You are correct. There is no way to reset a Game Center leaderboard category or to remove a category once it's been launched in a live app.
Apple did allow a way to reset an achievement.
The only work around that I know of is to just allow old categories to die, resort them to the bottom, change the label associated with the category to be something like "High Score (Archived)" and then create a new one and label it "High Score" and sort it to the top. This will give you a fresh one. But of course there is still a limit of 25 leaderboard categories - so at some point you're sunk unless you just figure out how to reuse old ones. (For example, make all your scores x10 so that everyone rises up above the old scores very quickly)
EDIT... In a recent version I actually did reuse a leaderboard category in a recent app update. The original use of the category was for scores that were fairly low... in the low 1000's. The new use of the category was going to be anywhere from 10x to 1000x that. So I knew that any old scores in that category would be erased within the first couple plays of the game. OF course the category id can't change (com.company.app.category), but the description (english or otherwise) can change. It can become confusing because you're using a category that has an id of one thing when saving scores for something totally different. But with #define kBlahBlahBlah to @"com.company.app.blah" you're code can use whatever name makes it easy to keep things straight. Hope that helps.