Normally the shipping quote is generated after the user enters their info for billing. If you are using Payments Standard you will have to use a different workflow. Are you currently gathering any of the customers details like city and zip before the checkout?
In order to implement the shipping quote charge you will need to gather this user info and use it in the shipping quote server behavior. When you apply the server behavior it will create the shipping quote for you that you can use in the shipping charge rule. Post back with any questions that you have about any part of this.
