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:
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.
Thanks! Yeah, I found the original illustration on a free vector site so I didn't need to do it anyway. I was supposed to be fixing up a "logo" for someone. I sure hope he didn't pay too much for it!