The volume is too low with the Nokia headset, using another one is fine. Have the microphone near your head.

I have no problems with media player and skype. No need to reboot either, actually on unix systems you reboot very rarely, this is not windows ;-)