I managed to solve the issue (if you can call it solving)....
Something wrong with the BESAdmin account.
I deleted the BESAdmin mailbox and the account
Deleted the SQL databases
Recreated BESAdmin, re-added persmissions, went through the entire document again to do a fresh install.
Added the users
They activated fine and started sending mail.
I am lucky that we don't depend too much on BES internally, unlike some of our clients, because it'd have a lot more issues with re-activations and upset people then I did internally.