I suggest that you talk to Apple -- if you have access to an Apple store, I would definitely take it to the Genius Bar and have them look at it.
The message you're getting is a kernel panic, the unix equivalent of Windows's BSOD. In Macs it is most commonly caused by a hardware problem, like a bad stick of RAM or an unsupported peripheral.
When I was using OSX.1, I would get a kernel panic without fail whenever I disconnected my Intuos tablet. For me the upgrade to Jaguar helped because 10.2 had better tablet support.
Unfortunately, headphones are not new, so it may turn out to be a small defect in the actual headphone socket board in your Mac. The fix may be inconvenient, but if this is a reproduceable kernel panic, then it won't fix itself.
If you can't do without your Mac, consider getting Pro Care. The $99 price tag is steep, but you do really get white glove service, plus a bunch of other stuff. A friend of mine needed a logic board replacement on his MBP and his turn-around time dropped from 3-5 days to 7 hours with Pro Care.
Hope all goes well!