I'm new to axolotls, but I've been doing the freshwater fish thing for decades, so I thought I'd jump in with my two cents. I know a lot of this is covered in the caudata culture fish compatability page, but I feel like I'm throwing a couple of other ideas in the mix, so I thought I would go ahead and post a reply:
The picture that began this thread is definitely a CAE, and it is not a good choice (someone already mentioned their aggression):
http://www.fishlore.com/profile-chinesealgaeeater.htm
The mainpage of fishlore has decent profiles of many algae eating fish, and a lot of threads on algae prevention. Things to consider: (1) armored cats = could get stuck in mouth. (2) suckermouths = likely to try to "scrape" any surface that will be still long enough, including amphbians, unless they're very well fed. (If you're making sure they're well fed, they might not have enough appetite left for the algae they're intended to eat.) (3) Temp will be an issue. If the temp's right for the axolotl, it will not be warm enough for the algae-eating cats that are common in the pet trade. (The lowest temp on an otto's range is 70; while ottos are peaceful and small enough, you need ~3 per 10 gallons for them to do the job. Also, they're difficult to acclimate to ANY tank successfully, most are wild caught, and any bottom dweller would probably be very easy axolotl snax.)
I'd second the vote for shrimp, especially if your lfs sells ghost shrimp cheaply, or if you breed your own red cherry shrimp (which I've contemplated doing as feeders/tank cleaners, as it's supposedly easy to do). Japonica shrimp are known as the best algae eating shrimp, but I don't know their temp needs off the top of my head.
Non-catfish fish: Some Plattys can overlap the higher end of an axolotl's temp range (68-72 should be fine for verigated platties, but swordtail plattys need tropical temps), and they do nibble algae. Also, since plattys are live bearers, they might reproduce more quickly than the rate at which they're eaten, leaving you with cheap replacements. Same goes for fancy guppies, except they're usually slow and clumsy because of their tails, so they'd probably be picked off much more quickly.
I'm a fan of feeder guppies, myself. They're less inbred than most fancys, and can stand cooler temps, and they move quickly. They'll definitely have ich when you buy them, so assume you have to treat that during quarantine, and expect 25-50% of your purchase to die off in the first week. (Ich meds are toxic to amphibians, so, once treatment is done, perform regular water changes, so it's definitely long gone from their systems before inclusion in an axolotl tank. Better safe than sorry.) The ones that make it through the remainder of quarantine will usually be pretty hearty. Give them a long quarantine and thorough visual inspection, though, because they really are in bad condition in pet stores. I would say the same of rosy minnows.
White cloud minnows rock and breed readily, but I haven't known them to nibble too much algae.
Don't forget that good ol' harmless pondsnails/small ramshorns will relish algae. There are other species that eat algae as well, but I seem to recall a thread about a newt getting its head stuck in a trapdoor, so that rules out most of the larger, freshwater snails.
One other thing that I want to say, and I hope is not taken the wrong way: if you don't already keep fish, it might not be a good idea to add them to an amphibian's tank. I simply mean that, if you already keep fish, you know what to look for as a sign of illness, and you know what to do to prevent illness, both of which means they're less likely to become ill and make other animals ill. If these things are brand new to you, then the odds of problems arising go up. It's just something to consider.
... and of course, don't forget all the warnings that are on the caudata culture pages Re: species mixing and fish compatability. The safest route would probably be to invest in a manual algae-scrubbin' pad.