Adobe Ideas, iDraw, Sketchup and Inkpad all allow you to import or paste photos and draw over them. iDraw, Sketchup and Inkpad have vector freehand line tools that convert into an editable vector line. Adobe Ideas smooths out a line very nicely that you draw but the resultant object is not a vector but a raster line. Inkpad seems to have the most "Illustrator" like drawing tools. iDraw and Sketchup are more CAD like apps. They all have merits in different ways. I think Adobe Ideas would be the easiest app to trace over a photo but it has very limited tools and not vector as I said. iDraw has a very interesting variable width (calligraphy like) Brush tool as well as an adjustable width freehand line tool that can be used to trace.
I am honestly not sure if anything would do what I was looking to do last night. I just had a couple of simple line-art logos sent to me as jpg that I wanted to convert. I ran them through Live Trace this morning on the laptop and they came out pretty good. But it doesn't sound like the iPad apps will do that (yet).
I will also take a look at Inkpad, don't know how I missed that last night.
Ideas is a vector app that acts like a raster app. If you send a PDF by email from Ideas and open it in something like Illustrator, you'll see that everything you drew is created using paths and fills, like Illustrator's blob brush. This video shows briefly how it can integrate with Illustrator.
But the best vector app I have ever used is vector magic. I use it on a Mac but i think there is a windows version too. I use it often when my clients only have their logos as a jpeg. Only time it doesn't work well is when gradients are used.