For this example, let's call your table scores:
Make sure you have a unique index
ALTER TABLE scores ADD UNIQUE INDEX user_category_ndx (user,category);
Now run this to replace:
INSERT INTO scores (user,category,score) VALUES ('username','mycat',127)
ON DUPLICATE KEY UPDATE score = VALUES(score);
If your updating the score means add up scores, then do this:
INSERT INTO scores (user,category,score) VALUES ('username','mycat',127)
ON DUPLICATE KEY UPDATE score = score + VALUES(score);
Give it a try!
UPDATE 2011-08-28 09:00 EDT
If you want to keep just high scores and then add the unique index, here is what you must do:
CREATE TABLE scores_new LIKE scores;
ALTER TABLE scores_new ADD UNIQUE INDEX user_category_ndx (user,category);
INSERT INTO scores_new (user,category,score)
SELECT user,category,MAX(score) FROM scores GROUP BY user,category;
ALTER TABLE scores RENAME scores_old;
ALTER TABLE scores_new RENAME scores;
#
# Drop old table if no longer needed
#
DROP TABLE scores_old;
UPDATE 2011-08-28 10:53 EDT
Run this to keep maximum score:
INSERT INTO scores (user,category,score) VALUES ('username','mycat',127)
ON DUPLICATE KEY UPDATE score = GREATEST(VALUES(score),score);