My instinct says that you will have to recreate it using the pen tool and/or gradient meshes. You're right, the image is much too small to produce a decent trace.
You may already have experience with these techniques but here are a few links that may prove useful:
Pen Tool: http://vector.tutsplus.com/tutorials/tools-tips/illustrators-pen-tool- the-comprehensive-guide/
Gradient Mesh: http://blog.spoongraphics.co.uk/articles/20-tutorials-to-help-master-i llustrators-gradient-mesh
That looks like an existing Illustration and unless you have the rights to the image or illustration I should say then you cannot recreate it or trace it without permission so don't worry about it start by creating you own art, If you have source materials then make sure you have the right to use that as well.
North America
Europe, Middle East and Africa
Asia Pacific