That sounds like my theory might be correct then. The default script execution time is usually 30 seconds. My guess is that the plugin fires off
gzencode on line 1029 of wp-db-backup.php then gets killed before it finishes.
Firstly, have you tried setting MOD_EVASIVE_OVERRIDE? Looking in the instructions & the code around line 50 suggests this might help if the backup dies prematurely.
I suspect though that that's for handling situations where the script times out during the actual creation of the backup file. If the backup file is complete then it's perhaps more likely to be caused by the
gzencode. Sticking a
set_time_limit with a large time limit just before the gzencode might fix things. Either that or stick some debug around there to see if it makes it into/out of that part of the code.
I can't really debug it myself because all my sites are small & the plugin works for me :-)