I'm getting the same error message but there are weights assigned to every product in the catalog.
I contacted FedEx and they told me PowerStore is pinging their testing server rather than their production server. I've verified that the "Test Mode" check box is unchecked... twice. I've also verified that I'm using their production code rather than their test code.
I accidentally tried running the shopping cart checkout the first time around with the FedEx production code in place, while the cart settings were still in test mode. I'm wondering if that didn't populate the relevant field with the test information and that field isn't reverting to the unchecked status as a result.