Lars,
I don't think adding a bunch of columns to users is a good idea. I don't think we need a complex solution either. We know that users will often have more than one IM. This looks like a two table solution would work. A list of IM types and a table of IM nicknames mapped to user_id.
This is extendable, but its not over designed, I think.
