When the Pans Ops speed classification system was introduced, both here and in Oz, there was a fair degree of confusion on this point. The basic situation here is that, if you can't meet ALL the requirements of the nominal category, you must use a higher category that allows you to meet all the speeds. Circling was certainly the major issue for many aircraft that are nominally in Cat. B, so they all had to use Cat. C.
And, before anyone asks, no you can't use a lower category on the basis of speeds for actual configurations. I understand that ICAO is about to change the basis of the speed categories in the near future, but it isn't likely to change the speed requirements in any of the segments.