First off, compliments with the logo. Looks cool.
Second, on to business: Illustrator has a built-in tracing tool you could use.
Just paste the image in and use
Object > Live Trace > Tracing Options...
Tutorial can be found here, or by googling around.
Play around with the settings until you're satisfied with the result. Protip: turn on 'preview' and then set it to 'tracing with outline' to see what you'll be getting.
Once you clicked 'make', don't forget to 'expand' it to create the paths.
Then you can just adjust the paths like you would normally do.
If live tracing isn't working for you, you can always trace it by hand with the pen tool (as stated by Amanda). This is slower and harder, but gives you more control.
Another option would be to use Photoshop's brushes to essentially redraw the image with your mouse/tablet. But the downside would be that you don't have vectors, so scaling isn't going to be as easy.