I dont have any experience with Alltel but dont see why the procedure would be any different from mine. Find the mobile email settings icon (envelope with a cog on it) This should take you to your carriers bis site. Log on using username and password and click send service books.
Go to BlackBerry Internet Service and set up a log-in if you have not done it - and on the left, there's a link 'service books' - then you get a page with a button to click to have them resent to your device.