You can colour your personal message using Messenger Plus!, no addons needed.
Set your nickname using colour etc. like so:
Then copy and paste it into the Personal Message box, but edit the text, and any colour codes etc. and press OK.
It'll appear like this on MSN Messenger:
Then it will appear like this to other people: