Unable to revoke 'super' privilege from user?

[David Hicks]

I have a legacy system that I inherited, and I'm trying to get security under control. We have a lot of users that have been given SUPER privilege out of sheer laziness. Most of them have been easy enough to fix, but I have a few that appear to be special cases.

When I run "SHOW GRANTS FOR" on these users, I see something like:

GRANT ALL PRIVILEGES ON `database`.* TO 'user'@'%'

I am unable to revoke the SUPER privilege from this user at all. I've tried a number of variations on the REVOKE statement. Using: "revoke super on *.* from 'user'@'%'" I get what appears to be a clean return but no effect on privileges. Adding the database to the statement results in this error:

ERROR 1221 (HY000): Incorrect usage of DB GRANT and GLOBAL PRIVILEGES

Any help?
I'm on MySQL 5.5.23.
Thanks,
David