But the slash in username is always encoded in %2F ??
What exact error are you getting? If you get a page not found then it's never reaching CB. Joomlas mod_rewrite rules appear to be conflicting regardless of it being encoded or not.
Adding User-ID in prefix is (i think) a good idea to solve this.
Some won't like it, but it seams to be the best solution. If a username contains invalid characters then the idea is to prefix with the user id. So this would only affect installs with usernames that aren't very URL safe.