I had the exact same problem when I opened my Facebook account. The appeal worked smoothly though. I guess if there is any kind of name checking going on (which I find useless) these things are bound to happen.
If you were to try to change your name on Facebook, they warn that it takes 24 hours and is done only after a review (probably automated though). Facebook has always had a policy of using real names - it just so happens that if you aren't always using it the system doesn't trip review (but active users are often faced with the dreaded "friending too many people" warning, or similar).