Are you in the US? if so then there is a bug affecting T-Mobile users, where Nokia Messaging does not show up. If you have an AT&T sim card available then you can put this in temporarily then you will be able to select Nokia Messaging as a service provider.

Once it is setup you can switch back to the original SIM card. I believe you should be able to set it up on WiFi if you don't want any data charges on the AT&T SIM.