After discovering that in some of the accounts I manage that the Find and Edit Max CPCs Tool was failing to put into effect the bid changes it said that it has saved, and noticing that the problem only seemed to appear in accounts where we were using Position Preference, my Adwords Rep confirmed last night that there was indeed a technical problem here.
If you are using the Find and Edit Max CPCs Tool on a campaign where Position Preference is enabled, the tool will not update your bids.
I've not tested to see whether any of the other advanced search & edit tools are being interfered with by Position Preference.
I can confirm that if Position Preference is turned off, then the Bid Tool does function. Warning: If you turn Position Preference off, you will lose all of your position settings. They are not saved and do not come back when you turn the feature back on.