That should be the method, did you put the proper attribute tags for your class so it catches it, and did you set your shipping to use this custom ICarrierProvider class?
[assembly: RegisterCustomClass("MyCustomShipping", typeof(MyCustomShippingProvider))]
public class MyCustomShippingProvider : ICarrierProvider
{...}
I have it set up the same way you do but i didn't run into a problem.