Reading that description of Klez, it looks pretty nasty. Searches everywhere for email addresses, then sends mail out through them. So if someone has seen your email address on a webpage, it can be used (doesn't have to be in an address book, looks like cache files from IE will work.) It can even select a random address that it finds and use that as the FROM address.
I'd be really, really surprised if UBB's security had been comprimised (and the only thing done was stealing of a few email address).