Hi, Im on a Jailbroken 2.2.1 T-Mobile UK, and got the feared "Cannot connect.." message, and could not connect to AppStore or Itunes over 3G or Edge.
Removing "com.apple.mobile.installation.plist" did not solve the problem - it just comes back after a reboot. I've tried rebooting it in several ways (Bossprefs, power off/on) to no avail.
Then I got tired of it and completely reinstalled the phone from scratch. After Pwning/Yellowsnowing, i did not recover the previous iphone data in Itunes, so that's a proper clean install. Without doing anything else, I tried the app store first thing and it gave the same "Cannot connect.."

Safari did work so connection was fine.
Then I entered my original o2 sim to which it was previously locked, and it did work..
But still not on T-mobile.
So, this problem is a little deeper than I hoped for, any ideas are very welcome.