Output volume control isn't working
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.