Imagino que no puedes descargar del market porque igual tienes el market antiguo y ahora ha cambiado. Se llama Google play. Si es así, para poder seguir descargando, solamente tienes que actualizar la aplicación del market (creo recordar que se actualiza sola). Otra cosa es que no la puedas actualizar porque ya no tengas más sitio para aplicaciones en el teléfono. Si es así, deberías de desinstalar alguna aplicación, actualizar el market y proceder como ya te he explicado.
Otra posibilidad para hacer hueco en tu teléfono es pasar alguna aplicación a la memoria externa. Si tu sistema operativo es Android 2.2 o superior, puedes hacerlo con algunas aplicaciones. Para verlo, vete a Aplicaciones --> Ajustes --> Aplicaciones --> Administrar aplicaciones. Pulsa sobre cualquier aplicación y si puedes te da la posibilidad de Mover a la SD. Este gesto con varias aplicaciones te permitirá tener más sitio en la memoria interna del teléfono para instalar aplicaciones nuevas o simplemente actualizar el market.
Si por el contrario tu problema es cualquier otro y no puedes descargar nada de ninguna manera del market, pues date por fastidiado. Solamente podrás hacer una copia de seguridad de tus contactos, SMS y poco más. Las demás aplicaciones, tendrás que reinstalarlas una vez que te limpien el teléfono.