If you had a legal name change, then you have paperwork that shows that name change - likely an amended birth certificate that is certified by the state in which you had the change done. Contact blizzard, explain this, explain you want to change the account name to match current information. They will have you fax copies of said paperwork in and you'll have your account name changed.

I agree with the red tape of a legal name change, having just gone through one myself last year to finalize an informal name change that occurred when I was 2 (1974)... such a royal PITA but finally I never have to explain why my ID isn't what people call me again.