Should I trust a website which breaks when I use a complex password?

Your description is that the site fails to properly validate their input. This (weakly) implies a deep flaw in their code. If your input had simply choked their routine that calls PBKDF2(), then your password hash might not have been reproducible; but I would expect a simple password reset should have been adequate to clear up that problem. Deleting your account might indicate that your account record was corrupt; however, deleting accounts might simply be their response to anyone who has a password problem due to unexpected user input. They might even be trying to actively thwart hackers with this response.

Also, flawed doesn't necessarily mean their site is vulnerable. The defective code would need to be exploitable, and you didn't supply evidence of that. Such evidence might include erratic behavior or inexplicably changed values.

If you decide to press further, perhaps testing individual password characters to isolate the glyph that caused their site to lock your account, know that they would be within their rights to consider those attempts to be a hacking attack. Seek the site owner's permission before experimenting.

Note that if instead of using high-bit-set characters, you construct your password from 16 cryptographically random, high-bit-unset, standard, ordinary, printable ASCII alphanumeric characters, the practical difference to your password's security will be irrelevant.

Most likely it means that (like most programs written by Americans) it's never been tested with Unicode characters and you've exposed a bug in their code. It's not a high priority for them to fix, so instead they've just sidestepped the problem by telling you to not do that.

It's strange that customer service deleted and recreated your account instead of resetting the password, but not incredibly worrisome. It could be that they're poorly trained to deal with this situation and that's just the approach they took. It could also be that the bug is also present in the password change feature for some reason (maybe they store something encrypted with your password as a key, and they have to decrypt it then recrypt with the new password?).

A site with these sorts of engineering and testing issues is likely to also have a security flaw or two, but that's a statistical correlation, not something directly implied by the observed bug.

Password processing should be one module that does not produce or verify more than a hash. The only ways in which a complex password cannot be successfully reentered is two separate pieces of code supposed to be doing the same thing but not doing so, or worse, passwords getting stored in plain text.

The more processing or storing is done to passwords in the clear, the more susceptible the site is for password extraction attacks or general attacks on the system.

There is an xkcd comic about password processing exceeding its immediate scope.

And of course this also is reminiscent of little Bobby Tables.

Summarizing both comic strips: sanitize input before storing it anywhere, and don't overprocess passwords.

I am sorry if my references are all by Randall Munroe but his explanations are so graphic...