You can add the Enhanced Voicemail feature to your phone for $1.99/mo. It increases the capacity from 20 messages to 40, and the time limit from 1 minute to 2 minutes.
Just hung up with ATT. The message length does not extend with the Enhanced option. According to the ATT rep nothing can change the lenght within visual vm.