Yo no se como puede resolverse, pero no veo que esas cifras sean malas. A mi me quedan menos de 30Mb libres, y me deja instalar sin problema.
Lo que te va a decir cualquiera es lo normal, sin saber detalles mas exactos de tu telefono... que muevas cosas a la SD, que limpies cache y esas cosas, etc... porque, entre otras cosas, mucho mas no se puede hacer.
Lo que si puedes hacer es intentar quitar las actualizaciones del Market, desconectar de Internet (porque el market se actualiza solo), e intentar instalar el apk "a mano", a ver si hay suerte.