I looked through Apple's forums and apparently this problem isn't easily solved. Basically, only a full reset (without restoring any backup) is guaranteed to solve the problem. That means starting from scratch, which is what I did.
3G is now back, but I have to play through all my Angry Bird levels again... *sigh*
This problem better not recur with the next update...