iTunes restore iPhone SIM Card no longer works.

Ok, I had all my contacts and information backuped onto my computer so I could easily transfer them from my 16GB 3G to my new 32GB 3GS. After being restored and synced with my computer my SIM Card no longer works. It wont let me place a call or text. When I un-plug the SIM Card and then plug it back in a message comes up saying invalid SIM and then disappears. Also it either has 1 "bar" with the rest flat and no AT&T logo or 3G, or says No Service.