Current turn around for all Premium Services is about 2 weeks. This is due to the large volume of requests we currently have, as well as some delays due to the recent downtimes - character transfers & renames can't be done if the worlds are down.
The system currently provides a confirmation page if the request is received, but no confirmation email.
You'll receive an email confirmation once it's been processed. That's also when you will be charged. This email confirmation will include directions for you to change the name... the process done by Turbine adds a rename credit to your character. Be careful, each one is only good for one use, so type slowly and double check before you hit enter!
DANG!!!! Two weeks. Well, this specific post was about character name changes, but the person did say "for all premimum services."