Microsoft updated their server protocol to prevent certain characters from working in MSN Messenger nicknames.

To use colours in your nickname download the latest Messenger Plus! by clicking here
Once done that, install Messenger Plus!

Go to a conversation window and type:
/nick "yournickname"
Press enter or click on send.
Replace "yournickname" with the MSN Messenger nickname you want :).

Note: If you don't want Messenger Plus! to automatically close all colour codes, then use /nick2 instead of /nick. This is an unsupported command.