I have seen a HP5510 working well on a Linux box, everything was supported pretty well apart from Fax from PC. I'd say go hp simply because they have the best Linux support.
http://hpinkjet.sourceforge.net
The 5510 is now end of life, but there is a replacement (6210 which is the same but with pictbridge and a better control panel)
There was a discussion about these devices on the list a few months ago so it may be worth greping the archives. I think the subject line was All in one printers.
The only missing thing from your feature set is 35mm scanning, but to be honest without a proper backlight (like on the canon lide 80 scanner) you get only average results with those film converters anyway.
They should be less than £130....anything much cheaper than that will be a sheetfeed scanner rather than these which are A4 flatbed with a 20 sheet ADF. However these are fax capable devices, models without the fax features will be cheaper if you don't need it.