After spending a few hours trying to increase the voicemail maximum message length inside the FreePBX admin page and asterisk configuration files, I found the problem was with Google.
This might save somebody some time:
If you would like to increase the time that incoming GV calls are allowed to leave messages on your pbx, first of all log into your GV account and under settings -> calls, check the box next to “Enable Recording (4), Switch (*) and Conferencing options on inbound calls”.
As well you will need to set the maximum message length in the voicemail admin module in FreePBX.
This thread led me to think about the problem coming from outside the pbx:
https://issues.asterisk.org/jira/browse/ASTERISK-11082