I just tried it:
Separate won't work, marge vertices didn't work for me but if it does, it might enable you to use cleanup successfully, otherwise that won't help either.
If my previous advise didn't work, you might want to try an advanced cleanup mel script (google it).
Benny