Character, character, character. You'll see that word pop up several times in any essay or comment I make on the forums when dealing with the performance side of magic.
Your outfit should properly reflect the kind of character you perform as. If you don't have a well defined character such as Burton (the sophisticant), Copperfield (the debonair), or Angel (the rocker goth) then your best bet is to perform in something that is as natural and normal to your audience as it can be. Penn & Teller say their choice of a gray suit reflects this. Because nothing is as invisible to the modern audience as a gray suit.
It's funny to note: That back in the early 1900's people wore good suits and tuxedo's to theaters. So, the magicians started wearing the tuxedo's to blend in with their audiences. To appear to be like one of them. Kind of funny how that image has evolved in modern times to be the stereotypical image of the working magi.
If you don't have a character you present as, I would say business professional would be acceptable. I'd personally go suit and tie, but that's just me. Tuxedo's are nice, but also pretty vanilla by this day and age. The important thing is: You need to be comfortable in it. If your not comfortable your performance will reflect that, and thusly suffer.
I would be very careful of going into the goth range of outfits unless your act and personality can support the image. 5 speed and other card tricks (as presented in the instructional information provided with purchase of the effects) do not translate well into the "goth" image without some minor personal tweeking.