I have the Lion OS, but no bluetooth headphones, so I can’t speak from personal experience. Sorry.
Noticing that no one had yet responded to your question, I thought I would do some Google-fu.
Looking in to this issue, I found a lot of posts detailing problems with bluetooth headsets after people upgraded their machines to Lion. Would appear there is a bug in Lion. Seems also that Apple may well know about it and is working on an update to address it. Well, that’s the rumor.
Anyway, I did come across a possible fix to your problem. “Spadecoder” on the Apple forums suggested this, in response to someone else having a similar problem: “Go to System Preferences -> Sound -> Sound Effects and change “play sound through” to “internal speakers.” Spacecoder goes on to say that that should solve the problem of the error messages coming up with the headphones paired, but turned off.
It’s worth a try.
Please let us know if this worked, or not.
Hope you are having a great day!
-Charlotte