There are so many tracers now, each of which works in a slightly different way. Gallium 68 is considered to be the most sensitive at very low PSA levels but some prostate cancers just don't show up on Ga68. F18 FDG isn't as popular for prostate cancer because much of the tracer is cancelled out by the kidneys so it doesn't get to the prostate, but F18 FDG seems to be very good at picking up mets. Then there is F18 FACBC (Axumin) which is what was being trialled at Leeds following excellent results in Italy, and there is also 18F DCFPyl which is good at picking up recurrence in the prostate / prostate bed.
These all seem to be more efficient than the standard choline tracer but each is slightly better for picking up cells in certain circumstances. If your Gallium scan didn't pick anything up, it may be that the mets are so tiny and so widespread that no tracer is going to see them yet; on the other hand, your particular prostate cancer may be more responsive to an 18F or F18 than it was to a Ga68