In order to get Skype working on iPhone over 3G, you'll need to setup a VPN connection to a VPN server.
Some operators tend to block PPTP ports and our option is to use L2TP (so far no blocking)

Configure VPN:
Choose General > Network > VPN and then choose Add VPN Configuration.
Select L2TP
Server address: enter an IP address of a server from the confirmation email
username and password: enter your username and password from the confirmation email
shared secret: enter the IPSec pre-shared secret key from the confirmation email
Click "Send All traffic over VPN"
Click Save.

VPN Setup is done and now you can connect