Checked with VZW Support via email. They suggested getting in touch with Nissan also.
So I did some more digging. It appears, based on looking at some other forums, that the problem is related to A2DP profile in Android 2.1. Also someone did get confirmation from Moto that it was a missing a profile in the Bluetooth stack. It appears that the problem goes away on Froyo.
I haven't tried this yet but supposedly this works:
I found a temporary solution for the G35. I assume the same can be done on the Altima. When you make or receive a call, click "Use Handset" on the screen in the car so that the call goes to the phone. After, hit the "Phone" button on the car. Now the call will be transferred back to the bluetooth, the sound will be clear and the other person will be able to hear you.
This is definitely not a permanent solution, but better than nothing. I won't be so inclined to return the phone now.