LOL! You can downgrade from MySQL 5 to 4 but you lose all your auto-incremental keys. Which means all your postids, threadids, userids etc is all lost.
So in the end, I upgraded back to MySQL 5.1 and for fun, upgraded to PHP 5.1 as well. The only snag with PHP 5 is an APC bug, but that's easily worked around.
My advice for vB users - once you upgrade MySQL, don't try downgrading.

It's a path of pain and suffering.