Matt Cutts told that overoptimization causes so called -950 penalty, check here: seroundtable.com/archives/013473.html
I would say you should be patient and build some quality links to it.

From GOOGLE US I see you at 100+ position, GOOGLE UK - 100-110 so its all ok.

You're not penalised. The site is indexed.

The site is relatively new and with hotels there are many strong sites which huge history which will always rank well.

I would perhaps check your backlink profile. Are there any links in there that could be hurting you? I saw a few which looked really spammy. I would look to address those.

I do think you have over-optimised the site. You need to tone it down a little. You don't need to go so far with it as you have done.

Tidy it up and keep getting good links, don't get spammy ones, they always hurt you when a site is new.

Hey Paul,

I'll start by telling you this very plain and simple, backlinks are not everything to do with SEO, the fact your competing with a domain which is over 13 years old, might suggests some problems, you might find that changing your websites title to "Find Hotels In Swindon" would work a bit better.

You shouldn't optimize your title so it makes less sense but carries a better SEO value, I can see "Find Hotels In Swindon" getting more clicks then "Hotels In Swindon", but that's down to you to change.

Just carry on building backlinks and updating your website, carry on checking your current ranking, look for a increase, figure out what your doing that's working and what isn't working.