If the feature is correctly on your account it should allow you to change/set the greeting by selecting 'phone' then 'voicemail' and then 'greeting'. *86 or dialing into vmail shouldn't work on iPhones as they use a visual vs dialing program. Do you receive some sort of error message when trying this?
Gotcha, has the voicemail ever worked since you've been using this phone? That message could mean the voicemail feature is missing from your account itself (it can be added thru customer service) or there is some sort of incorrect forwarding on your line which you can check to ensure it is off by dialing *73.