Si, si, a mi también me salió "not found" y pensé que no habría funcionado pero reinicié el teléfono como indicaba en el enlace y probé a descargar del Market y perfecto!
A decir verdad, probé tal cual dice aquí:
Market download problems? Open app settings. Go to Market, force close, clear data/cache, reboot to recovery, clear dalvik-cache. If this does not work, then open an ADB console or a local terminal on the phone and type "m2sd memcache enable". Then reboot. (Remember to enter "su" to grant superuser rights)
Hice lo primero de forzar cierre y clear cache, reinicié en recovery y dalvik cache, pero nofuncionó.
Entonces hice el segundo paso como he dicho y solucionado. Puede ser que haya que hacer los 2 pasos si no va el primero.
Ya contarás.