I prefer not to get domains registered through web hosting company. It is cleaner to have domain and hosting separate, if possible. It may be cumbersome if you decide to change hosting company in future. Also your doamin should be under full control of you, not your hosting company...
You can go tohttp://registrar.godaddy.com/ (or someone cheaper) and get new domain registered through them. Then request your hosting company that you want to park (or replace) this new domain over your existing domain. Get DNS details from them and set the same in your new domain using registrar’s ‘Domain Control Panel’.
Cheers,