What cabins are available when you ask them to check availability? The way BA do award space searches only shows them the redemption classes, for example:
Z2 U4 P3 X7
Silly question, but are you sure there's a first class cabin on the aircraft, and you're not saying F but mean J? BA agents should be offering J if that's the case, but shouldn't be declining F/Z if it's truly available.