You need to set the php max execution time higher and memory limit higher. You can do that in your php.ini.
My default phpMyAdmin installation that came with my server has the same problem as you.
I installed another newer version on the side and this worked fine out of the box, so i am backing up 280Megs of database without problems..
After set php max execution time to 15 Min still was the error,
I tryed to backup my Database with mysqldumper (
www.mysqldumper.de
) and it works great B)