If the inability to change permalink structure on free hosted WordPress.com blogs is a deal breaker for you then you can hire a web host and set up a WordPress.org install.
For more on the differences: http://support.wordpress.com/com-vs-org/
That changing a blog address feature is deactivated while Staff work on it. If you have posted the error message you received above then I would not have replied as I did. The notices tells you to try agin in a few days and that’s what you must do.