Try adjusting the volume with headphones in.
Try adjusting the volume AFTER plugging in the headphones. OS X keeps track of volume from internal speakers separately from plugged-in speakers. So if you happened to have turned it way down the last time you had headphones plugged in, then even if you had the volume on maximum the instant before plugging in your headphones, the headphones would be muted. (This is precisely to prevent you from accidentally plugging headphones in with the volume on maximum.)
For example, my 'standard' volume setting is 3/4 for internal speakers, 1/2 for headphones. If my volume is at 3/4, then the moment I plug in headphones, it drops to 1/2. The moment I unplug the headphones, it jumps back to 3/4. If I adjust the volume while the headphones are plugged in, it will still go to 3/4 when I unplug the headphones. (Which can make for a rude surprise if I had volume on max for some reason, and was listening on headphones at near minimum. When I unplug the headphones, it gets LOUD, quick.)
It doesn't even respect 'mute' across the two. (So if you had it muted with headphones plugged in, but not on internal speakers, then when you unplug the headphones, you'll get your sound blaring out.)