Had the same problem with my girlfriend's wii. i discovered after we both rebooted ours, that she managed to get hers back on before i did. I could send her messages, but she couldn't send me one. The trick is, your friends have to have their wiis online when you turn yours on. Then you must do the same for them. Not sure if it's a requirement, but i recommend being on the BIOS screen (main menu) when waiting for friends to come on.
