From what I read in these forums, the earphone jack in many of the macs, shall I say, leave a lot to be desired. Try "playing" with the headphone jack in the plug, possibly not pushing it in all the way. Do this of course while listening. See if you can find a position that works.
The problem may be that the tolerances of the tip and ring connections may either be too fine or not fine enough for the standard 3.5mm stereo jack.
Bottom line, this may be a physical problem with these jacks and nothing wrong with your software.
My new macbook pro also has this problem. once the headphones are working, say they're connected upon startup -- then if the headphone cable is disconnected, to replug it results in no connection.
Only "fix" I have found so far (tried different connecting cables) is to restart, with cable plugged in before the restart. Annoying, but not so much as to cause me to send it in for service.