So, who or what are you leaving a message for when testing and are you an identified user or an outside caller?
There are 3 places to check for message length that I know of.
1. In the Advanced settings under: Advanced | Telephony | Maximum Recording Time in Milliseconds. This defaults to 1200000 ms (20 minutes) and is global - it should over ride any other settings (although I haven't tested this in some time).
2. If you're leaving a message for a user or call handler as an outside caller (unidentified caller) - on the target user or call handler on the Message Settings page the Maximum message length (defaults to 300 seconds).
3. If you're leaving a message as a logged in (identified) user, the COS you are assigned to dictates your recording length, the Message Length value defaults to 300 seconds.