I really don't know how this ever worked ...

From the looks of this code, you only have one setting on the Handling Fee and not a number of them, correct?

If so, see what happens if you use this for the $methods[]:
Code:
             $methods[] = array('id' => str_replace('_', '', $rateReply->ServiceType),
                                 'title' => ucwords(strtolower(str_replace('_', ' ', $rateReply->ServiceType))) . $transitTime,
                                 'cost' => $cost + ( strpos(MODULE_SHIPPING_FEDEX_WEB_SERVICES_HANDLING_FEE, '%') ? ($cost * (float)MODULE_SHIPPING_FEDEX_WEB_SERVICES_HANDLING_FEE / 100) : (float)MODULE_SHIPPING_FEDEX_WEB_SERVICES_HANDLING_FEE) );