BB Maps should already be installed on the Alltel Curve. Try resending your Service Books. Also, double check to see that you haven't hidden the icon or moved it into a folder.
I too have the 8320, infact it's the second one I've had and thi latest version doesn't appear to have maps... If I go into options advance etc its all there but I cant get the desktop icon to appear...
AT&T has the icon blocked from displaying in an attempt to
get users to sign up for TeleNav. There is a workaround to get it
to display and if I can find it, I'll post it here.
Google Maps, Nav4All and amaZeGPS all work just fine on the AT&T
8310. Maybe try one of those.