Thanks Dapi but I've finally found the problem.

On closer inspection of that table I discovered it has a function based index based on a function in schema A. Directly granting execute to that function to user B now allows user A to run the query.

Can't believe I didn't spot it sooner, D'oh!

Regards