The sound volume in the menu bar and the volume button on my keyboard doesn't change the output volume when I connect headphones or external speakers on my MBP. When I go to System Preferences -> Sound the Output volume bar does work. Any clue?
One thing to check is that your desktop volume control is actually connected to the device whose volume you're trying to control. In Lion, Alt+clicking the volume icon allows you to switch its function (and that of the keyboard shortcuts) between all connected output and input devices, plus any software devices such as Soundflower or Boom that might be running. I do find that it occasionally gets confused when plugging/unplugging devices, although not usually with simple headphones/speakers.
I've had this happen to me intermittently, but have never been able to identify a source for the problem. Even though it seems inconvenient, the thing that fixes it every time: restart. Give it a go.