Во-1, проверьте файрволы. Avast, DroidWall и прочие.
Во-2, снесите замусоренный /system/etc/hosts — наверняка он забит паранойей от AdFree или RomToolbox\Ad Blocker. (точнее она не паранойя, но файл может иметь ненужные вхождения)
В-3, снесите через, например, Titanium Backup маркет и попробуйте стереть данные
связанных с ним служб. Инсталлируйте
Google Apps заново
В-4, попробуйте альтернативы
alternativeto.net/software/android-market/
В-5, к этому времени система у вас будет настолько расшатана и убита, что проще станет накатить новую стабильную прошивку.