On one of our sites this was caused by the warehouse bod entering a really long value in the 'Title' field when adding the shipping tracking code to the order.
This only just started happening because the courier had changed, meaning that instead of entering "ROYAL MAIL 48" they were now entering "UK MAIL EXPRESS PARCELS (Next Day)". I shortened this to "UK MAIL" on the shipment page for that order and it went through fine.
Detailed instructions:
- Go to "Sell On eBay" -> "Sales".
- Click on the row of an order which has an error (note DON'T click the order number or else this takes you to the Magento order info, rather than the eBay order info). Note that on the eBay order details screen the "Order Log" box in the bottom left has an "Error" message as the most recent entry (at the top).
- Click on the "Magento Order #" link and a new tab/window will open.
- Click on 'Shipments' on the left and then click on the shipment row.
- In the "Shipping and Tracking Information" box, add a new entry - enter "UK MAIL" as the Title and copy/paste the tracking number from the existing entry. Then click "Add" to confirm this.
- Delete the old tracking info row by clicking the "Delete" link on the right.
- Close this tab and on the eBay order details tab click the orange "Resend Shipping Information" button.
- If everything has worked correctly, the "Order Log" box in the bottom left will now show a "Success" message.
I don't know what eBay's character limit is, but you could easily find out by shortening the shipment title by one character each time and re-sending until it works.