This was posted on Gizmodo, but they suggest that after you get the -4 error, just leave your phone like that. Worked for me after about 15-20 mins.
http://gizmodo.com/5024334/how-to-fix-iphone-and-iphone-3g-activation-woes
http://gizmodo.com/5024334/how-to-fix-iphone-and-iphone-3g-activation-woes