The main one is that, at least with the providers I used (three, including Fedex) there was no api and no way to interface with their systems automatically, everything had to be done through archaic websites with a usability designed before the dot com boom or by phone. During busy times (christmas shopping, for example), we had several interns dedicated exclusively to handle sending the info (number of packages, destinations...) to the supplier and printing the shipping labels.
I think that when you reach the thousands of packages per day, you are offered those services, but as a small setup with 'only' hundreds of packages, the only option was to do it manually. We had a simple system to handle orders, inventory, manufacturing... It would have been a breeze to integrate an api with it to print the labels automatically to give the guys actually preparing the packages.
We didn't get a lot of issues that usually pop up when talking ecommerce (scammers, false orders), we didn't even get many returns (I only remember a couple of cases) but we did get a few packages that disappeared in transit with no explanation or, obviously, a refund. The process to report those was horrible, similar to cancelling a mobile phone contract and in most cases we had to simply write-off the package and send a new one to the customer (actually, we are waiting for the resolution of a case when a package worth a few thousand euros was lost, we might actually get back that money).
Another thing that was annoying, although I know it's understandable, is that to start getting discounts they require a volume that, as a new company or sole trader you are simply not going to get. Paying the normal rate for Fedex, for example, makes packages quite expensive when you are talking international (and the fact that I live in an island with a population of less than 10M people doesn't help). We basically kept shipping costs to a minimum by eating into our profit margin. We got less money, but helped improve the sales.