(the only way around this is to let small inputs age for a few years).
Miners aren't paying much attention to the age of inputs these days, especially since they're likely all aware that the priority status for a given input will be removed from the code by the end of the year (slated for version 0.15).
The new rules arn't in force yet though, are they? Which means the old rules about priority still stand. If OP's output is made up of lots of fairly young inputs, that's the reason he is having trouble.
Incorrect:
The mining of transactions based on their priority is also now disabled by default. To re-enable it, simply set -blockprioritysize=<n> where is the size in bytes of your blocks to reserve for these transactions. The old default was 50k, so to retain approximately the same policy, you would set -blockprioritysize=50000.
https://github.com/bitcoin/bitcoin/blob/v0.12.0/doc/release-notes.md#relay-and-mining-priority-transactions
The miners can factor in priority if they want, but they do not have to. If I'm correct, most miners in fact do not use priority nowadays.
@OP: Post your TX ID or the fee rate (as suggested by Carlton). In case that you don't know how to make this trivial calculation, post the transaction size in addition to the fee included.
