I don't think the 32pix-tiles are too big for that resolution.
But the problem is, the menu is 704 pix broad right now.
Since we got 2 empty spaces, there might be a way to get below 640 just by editing the menuconf.tab. The bad thing is i don't know how it works and ther's hardly any documentation on this.
There are also vague plans to make the buttons smaller, but that's some more effort and you have to edit the menuconf tab too.
Edit: there is some documentation inside the menuconf.tab file itself. So maybe you can dig into this wofic, and find out how to shrink the menu, I'll supply the grafics and the rest.