Possible reasons (other than Open Firmware Password Protection) for not being able to boot into single user mode? Recently I was attempting to install some new software for a user. I followed these instructions to create a new admin-level account but when I held down cmd+S while booting it still booted into the regular login GUI, rather than into Single User Mode. The user doesn't have Open Firmware Password Protection installed -- what other reasons could there be for cmd+S not working?
Core Storage

If FileVault 2 is enabled for the OS X startup volume, then EfiLoginUI will present a graphic login dialogue before the start of OS X – seconds after the startup chime. 

If the startup key combination is timely, then startup should proceed to single user mode after a user's passphrase has been entered. 

Firmware

Whilst I don't know the model of your Mac, I can draw attention to a 2011 topic that was resolved in MacRumors forums: 


Mac Mini won't recognize Apple Aluminum Keyboard startup keystrokes


Wireless keyboards

Apple Wireless Keyboards: Using startup keys

If I recall correctly, one type of Apple wireless keyboard is (or was) known to be problematic … at the moment I can't find a reference – sorry.