This is very odd.

I propose the following: ask your SEO company to put into writing what they told you by phone and to send it to you. I can give you and unbiased opinion if you send me their reply by private message. Please note that while I'm not an authority in SEO and I do not do consulting, at least I think I can help you determine if your SEO company is telling you something that makes sense or not.

Also ask them to give you a detailed quote on this 1250 quid job to "fix" your site's position. I agree with Bex when he writes that the amount is extremely high for such a job.

Cheers

Jorge