My blackberry curve 8520 went from AT&T to GSM today and now my Blackberry Messenger doesn't work. Does anyone know how I can fix the problem?

Take the battery out and put it back in.

Could also be a tower/network issue in your area.

I've done that twice already and it stays the same.

I've also done he Host Routing thing but it says Registration qued.

Did you inadvertently turn off the data services on your device?
(Doubt you did.)

I suspect this is a localized tower problem with your carrier.

Nope it's still on.

Report the outage to your carrier.