Recently my hosting company changed the site setup so www.domain.com redirected to domain.com. All of our link building has been around www.domain.com as the site has existed in this way since launching a couple of years back. Whilst I appreciate a 301 redirect ought to resolve the issue, are there any down sides? Should I have the hosting company change it back?
Yes. You should use 301 redirect which is permanent redirect and there not problem after using 301 redirect.
I don't know what people want to say when they tell you yes, but you can just start using the non-WWW version. Just make sure to set a preferred domain in Google Webmaster Tools. If the whole site redirects then there's no need to do anything else for redirection.