I always understood that a 5-foot step was a 'no action'.
The 5 foot step is listed in the miscellaneous action section of both the SRD and the PHB. As it's an action and not of a type granted while slowed, it can't be used.
Under the same section treatment is given to activation of a feat and skill. "Use feat" says there are two types of feats: some which take actions and some which don't. Those that take actions are assigned actions by the feats themselves, such as Whirlwind Attack's full-round action. Denying usage of a feat would only occur if the feat itself took a full-round action, just like Whirlwind Attack. "Use skill" says most skills take a standard action, but could take other actions as stated in the skill description. Denying the use of a skill would only happen in a full-round case or one which uses multiple rounds must be used like Disable Device, I suppose.
Notably the the other two miscellaneous actions say to refer to other portions of the book for their type of action. 5 foot step is an action, but not one of the defined types. However, it does have specific conditions for use: no other movement, can be slipped between any other actions, only in non-hampered terrain or in darkness, must have a speed of 5 feet or more, must have a listed speed for that mode of movement. Of course, I could be missing some FAQ clarification or Sage ruling.
Edit: Rules Compendium page 90 says you can take a 5 foot step at any time so long as your movement isn't hampered or prohibited. Also, no language on actions on this version of the 5 foot step. I think this closes the book on it.