I had the Rockband set sent in the same box as the Dinobot set, by the USPS (through Australia Post)... so size shouldn't be an issue.

Not sure why either box would be rejected, unless they put in something else as a freebie that they shouldn't have, or declared it wrong.
When the sender gets it, see if there is anything noted on the box as to why it was rejected.