I never had much luck with that AJAX plugin either, but ViperBond’s Regenerate Thumbnails works perfectly for me on a number of sites: viper007bond.com/wordpress-plugins/regenerate-thumbnails
It manages several thousand images on my server, albeit somewhat slowly, although you can also run it on individual images or batches of images from the Media library.
If you have custom sizes specified in your functions file, it will generate those, as well as the ones specified in the Media settings. My theme has about a dozen different image sizes, and it does all of them, plus the standard defaults, with no problems.
This plugin is one of my must-haves for one particular site, as they get a new design every year, and sometimes the old post thumbnail/featured image size doesn’t work with the new design, so I have to run this reasonably often, on an ever increasing number of photos 🙂
Batch processing
For large media libraries it might be a little slow. It has successfully managed several thousand photos on an overnight run on one of my servers, but on others I find it times out sometimes. Then I just change the number of photos displayed in the Media Library to some reasonably sized batch, like 500, and “select all” on that page and run the regeneration page-by-page. That can be somewhat painful, but you can find a batch size that works for you if your server doesn’t cope with the full library regen.