Hey vegastime,
Sorry to hear that you encountered such a problem as well. I got this problem when I plugged in my iP4 for the first time and tried to sync. Here's a link at apple's site that you might want to try:
http://support.apple.com/kb/ts1275
Unfortunately, I tried and none worked for me. So I had to bring it back to my service provider and asked them to reset the software for me. Not sure if your provider can do that for you though.