@Samuel - A DBA would be ideal because people/venues that hire you could write checks to you under both your stage name or your legal name and when it comes time for taxes, you can work with both. It will just make conducting a legal business a lot easier.
Naming is definitely an important part of establishing a brand, especially in the magic world. It could take years of exploring different ideas until you settle on something that you want to stick with long term. As Ibimania pointed out, David Copperfield, for example, was objectively challenging to market because of the length, the opportunities to misspell it, and the fact that it was originally a wildly popular book from 1850 written over 100 years before (our) David Copperfield was born. But against the odds, he made the name work for him.
Another great example of a creative stage name is Justin Kredible. It's a common brand idea for anyone with that name (Justin Time, Justin Case, Justin Space, etc), but it worked perfectly for his demographic when he started. It's catchy, creative, and
kool. Even in his case though, he eventually changed his brand back to his real name, Justin Willman. In the end, some could argue that there is no right or wrong way to name brand. Using your real name, like Luis does, will make life a lot easier. But, if you have a overly common name (John Smith), or you think you would be better off with a pseudonym, then be careful and take your time before committing to it. I know from personal experience that using a cheeky/funny name for your brand can get old
really fast. I'm a designer by profession, and for the first 3 or 4 years, I went under the username "krazytim." I was 14 or 15 when I thought of it, so I didn't have the foresight to realize how unprofessional that was. I have used my real name ever since and still wish I started off with it.
Louis CK's real name is Louis Szekely.
Tom Cruise's real name is Thomas Mapother IV.
Olivia Wilde's name name is Olivia Jane Cockburn.
Clearly, we don't have the luxury of choosing our own names when we are born.
A list of 55 examples:
http://thoughtcatalog.com/nico-lang/2013/08/55-celebrities-whose-real-names-will-surprise-you/
Another excellent resource/podcast on naming:
http://99percentinvisible.org/episode/title-tk/
I wish you the best of luck picking a brand/stage name, and of course, with the magic special!