Pues te puedo decir que, más o menos, es exactamente lo que hice yo hace un par de días cuando cambié la de 2 GB que venía de serie por una de 16GB clase 6 que compré por eBay y... me pasó la misma putada que a ti. Sé que no tiene mucho sentido, pero aunque volviera a poner la antigua SD, no me reconocía ninguno de los programas que había instalado. Al final, opté por la opción más drástica... reinstalar la ROM y empezar a instalar las aplicaciones de nuevo...
Ánimo y un saludo.