Make sure you're following the instructions from Apple on safe booting:
To start up into Safe Mode (to Safe Boot), do this:
- Be sure your Mac is shut down.
- Press the power button.
- Immediately after you hear the startup tone, hold the Shift key. The Shift key should be held as soon as possible after the startup tone, but not before the tone.
- Release the Shift key when you see the gray Apple icon and the progress indicator (looks like a spinning gear).