I could easily suggest changing InnoDB settings which might be a littel heavy-handed just to get a mysqldump to work. You may not like what I am about the suggest, but I believe it's your best (only) option. Here it goes:
SUGGESTION #1 : Disable extended inserts
The default setting for mysqldump would include clumping together hundreds or thousands of rows in a single INSERT. This is known as an extended INSERT. It is causing some overrun beyond just max_allowed_packet.
I answered a post back on
Sep 01, 2011 (MySQL server has gone away obstructing import of large dumps) where I discussed doing the same thing for importing a large mysqldump. I believe disabling extended INSERT would help with creating a troublesome mysqldump as well.
mysqldump -u root --skip-extended-insert -p maia > maia.sql
Bad news: What this does in create an INSERT command for each row. This will definitely increase the time it takes to perform the mysqldump. Consequently, it will also increase to time is take to reload (probably by a factor of 10-100.
I have discussed
SUGGESTION #2 : Dump binary data as hex (OPTIONAL)
To make the mysqldump's binary data more byte portable, dump such data in hexadecimal
mysqldump -u root --skip-extended-insert --hex-blob -p maia > maia.sql
Bad News: It will bloat the mysqldump a little more
GIVE IT A TRY !!!
Side Note : The maximum size of max_allowed_packet is 1G