I have seen a couple of people talk about losing their visual voicemail after adding the custom ipcc file to get mms and tethering on 3.0. My Visual Voicemail works on 3.0, but I would get the messages pretty slow. I just saw this on another forum and tried it, tested my visual voicemail and it came through very quickly. The slowness may have been an AT&T thing, maybe not, either way if yours doesn't work at all, there is no harm in trying this.
In Settings>General>Network>Cellular Data Network
Under voicemail...it it says wap.cingular change it to acds.voicemail and restart your phone.
You can always put it back to wap.cingular if it doesn't work.