I use Pedometer Ultimate (no link, but the developer is Viaden). It does detect elevation changes, but I couldn't say how accurate they are since I typically ignore that information.
Beyond that, it tracks steps, distance, calories, time and speed. You can bring up the map and even see where you walked. It has a lot of good features. It can also do reports and stuff. For example, in the past 365 days I've walked 165.2 miles, it took 53 hours and 22 minutes, burned 20,923 calories and so on. I've also climbed 14,318 ft and dropped 14,224 ft in that time (makes sense since I usually end where I start). You can also track body measurements and such daily.
The only problem with the app is like some developers, they have WAY too many pedometer apps in the store and it's hard to tell the difference between them. Very confusing. I finally picked one that had an icon I liked and went for it.