Now you've proved that phone and laptop are talking the same language, I suggest you give your ISP a call and ask them if there are any specific settings / phone numbers for use with mobile dial up. Unfortunately there are too many variables to speculate as to why your phone is not connecting. When you tried the internet connection, was your phone actually dialing before you got the error message?
FWyg