Menus = PHP Warning: implode()

I cleared out some unused entries from the DB

Manually or with a plugin?

Do you (or your host) have a backup of the database?
Can you login?

First create a backup of the database as it is now:
http://codex.wordpress.org/Backing_Up_Your_Database

This could also be from something else not working properly.

Try:
– deactivating all plugins to see if this resolves the problem? If this works, re-activate the plugins one by one until you find the problematic plugin(s).

– switching to the default theme to rule out any theme-specific problems.

I don’t have a backup from today after I loaded a load of stuff on….

But do you have a backup from before you worked on the database?

From looking at the error it’s this line from the function start_el() that is causing trouble:

$output .= '<input type="hidden" class="menu-item-classes" name="menu-item[' . $possible_object_id . '][menu-item-classes]" value="'. esc_attr( implode( ' ', $item->classes ) ) .'" />';

I will look in my database if I can find anything related to this. But I think it’s best you restore to an earlier backup (if you have one).

I have gone back and restored the items I removed from the wp_terms table

How have you done this? From a backup?
Are you sure you didn’t do anything else, like updating plugins, or WordPress before the error occurred?

I think my next option is to start a new DB :'(

This could be an option (but don’t do it right now). As you can still login I would first export your site at wp-admin > Tools > Export.
You can later import your site if needed:
http://codex.wordpress.org/Importing_Content