I work for a removal company, and completely agree with the advice you've been given already.
I'd also suggest checking out their reviews online - but do keep in mind that things do sometimes go wrong with removals, and people do get emotional about it when they do - so one bad review among a bunch of good ones shouldn't taint them completely.
Since you're moving some distance, stick with the brands, rather than a man and van.
Don't take a quote from someone who doesn't come out to see the scope of your move, since it isn't a local move.
Don't just take the cheapest quote, base your decision not just on the quote amount, but also on the customer experience when contacting them, the surveyor, etc. And definitely make sure you get a all-in price rather than an hourly one!
You can also try and negotiate a bit with the price, if you really like a company but their price is a smidge high. Whether they can or will depends on a lot of factors, but it never hurts to ask.
Also, check if yoiur homeowners or contents insurance will cover you when moving - if it doesn't ask about the removal company's insurance options. With a move of this distance, it is absolutely best to be insured.
I work for one of the members of Britannia Movers (it is like a cooperative, each branch is independently owned and operated), and would recommend them as a whole.
http://www.britannia-movers.co.uk/