I've put 35mm C41 through Fotolab (in Pitt Street, between Park and Bathurst, right in the CBD) without problems and fairly rapidly, an hour or less. They tell me that they are set up to do 120 C41, but I don't shoot much colour and the last roll of 120 C41 I had processed was at Vision Graphics at Waterloo. As Fotolab is consumer oriented and Vision Graphics is pro, at this time of year it may be that Fotolab is more active.
I've just checked Fotolab's website, but they must be updating it, suggest that you check yourself later.
Regards - Ross