Magento – Fedex rates not showing on checkout

Enabling the fedex plug in doesnt show any rates on the checkout page in magento 1.8. Even the heading is missing from the shipping options. I have enabled the shipping option and also enabled Show Method if Not Applicable but it still doesnt show.

Im looking for any ideas as to why this might not be working.

Further to that, the shipping_fedex.log seems clean and there is results for all the different methods. Ill show a small snippet of the log to not bore you

[result] => stdClass Object
    (
        [HighestSeverity] => NOTE
        [Notifications] => Array
            (
                [0] => stdClass Object
                    (
                        [Severity] => NOTE
                        [Source] => crs
                        [Code] => 819
                        [Message] => The origin state/province code has been changed.  
                        [LocalizedMessage] => The origin state/province code has been changed.  
                    )

                [1] => stdClass Object
                    (
                        [Severity] => NOTE
                        [Source] => crs
                        [Code] => 820
                        [Message] => The destination state/province code has been changed.  
                        [LocalizedMessage] => The destination state/province code has been changed.  
                    )

            )

        [Version] => stdClass Object
            (
                [ServiceId] => crs
                [Major] => 10
                [Intermediate] => 0
                [Minor] => 0
            )

        [RateReplyDetails] => Array
            (
                [0] => stdClass Object
                    (
                        [ServiceType] => FIRST_OVERNIGHT
                        [PackagingType] => YOUR_PACKAGING
                        [DestinationAirportId] => YEG
                        [IneligibleForMoneyBackGuarantee] => 
                        [OriginServiceArea] => PM
                        [DestinationServiceArea] => A3
                        [SignatureOption] => SERVICE_DEFAULT
                        [ActualRateType] => PAYOR_ACCOUNT_SHIPMENT
                        [RatedShipmentDetails] => Array
                            (
                                [0] => stdClass Object
                                    (
                                        [EffectiveNetDiscount] => stdClass Object
                                            (
                                                [Currency] => CAD
                                                [Amount] => 0.0
                                            )

                                        [ShipmentRateDetail] => stdClass Object
                                            (
                                                [RateType] => PAYOR_ACCOUNT_SHIPMENT
                                                [RateScale] => 0000000
                                                [RateZone] => R0014
                                                [PricingCode] => ACTUAL
                                                [RatedWeightMethod] => ACTUAL
                                                [CurrencyExchangeRate] => stdClass Object
                                                    (
                                                        [FromCurrency] => CAD
                                                        [IntoCurrency] => CAD
                                                        [Rate] => 1.0
                                                    )

                                                [DimDivisor] => 0
                                                [FuelSurchargePercent] => 1.5
                                                [TotalBillingWeight] => stdClass Object
                                                    (
                                                        [Units] => LB
                                                        [Value] => 1.0
                                                    )

                                                [TotalBaseCharge] => stdClass Object
                                                    (
                                                        [Currency] => CAD
                                                        [Amount] => 40.8
                                                    )