Using redsnow or JB to activate the phone after restore. The sim iPhone will ask you to enter a valid sim after you restore. Try resetting the network settings after you JB and UL with ultrasnow because usually did the trick for me whenever I unlocked iPhones for Tmobile.
Hactivating is an activation that occurs without using an official SIM. Pwnagetool and Sn0wbreeze can put hactivation inside the custom firmware, and you can also be hactivated by Redsn0w.
Once, and once only, I had an issue of not getting service on a 3G after hactivating. Maybe that's source of your troubles. I would highly recommend getting your hands on an AT&T SIM (pre-paid, or burnt) and using that to activate your iPhone, and then unlocking with ultrasn0w.
^^^ like they said don't hacktivate but activate!
ultrasn0w should work if you have the iPad BB; are you downloading it from the official source?
Here are some instructions: http://www.iclarified.com/entry/index.php?enid=4253