We've always said free transactions may be processed more slowly. You can help ensure your transactions go through quickly by adding -paytxfee=0.01.
Good solution.
And it would be even better to expose this clearly in the GUI! Instead of hiding it as a command line option