I was having the same problem, double check your settings. My problem was step 6b I had the MEID Hex instead of the ESN HEX.
Taken from post #122
1) dial ##778, enter in 000000 for the password
2) copy the ESN(Hex) Exactly how it is(you need the caps)
3) click View Info in the lower left corner and click M.IP Settings
4) Change MIP_MODE to Simple IP Only
5) Click View Info again and goto Security
6a) HDR AN AUTH User Id =
5555555555@alltel.net (fill the 5's with your 10-digit number)
6b) HDR AN AUTH Password = (Your ESN(Hex) With CAPS)
6c) PPP USER ID =
5555555555@alltel.net (Same as above)
6d) PPP PASSWORD = alltel
7) Click OK in the top right corner and save and reboot.
Goto Start->Settings->Connections->Connections
9) Click Manage existing connections
10) Select Alltel Wireless and click Edit...
11) Click Next in the lower right cornder until you get to the user name and password screen
12a) Username is
5555555555@alltel.net (Same as above)
12b) Password is alltel
13) Click Finish in the lower right corner
14) Enjoy alltel wireless internet!