Do you have a backup?  If so, revert to that.  If not, you need to reset your blockchain by going to reset in the preferences and then chosing the disconnect.  When the app reopens, it'll redownload the last 52 weeks of blockchain. [Happy Anniversary Goonie]

Once you're back to a state with no pending transactions, send yourself the whole balance to a different client (like your desktop/laptop).  The fee you tried to pay isn't actually 'paid' until its mined, so you won't lose that .0005.  Once you send that tx, it should successfully get relayed.  From there, you can use your other client to send the two transactions to their original targets.  It seems that by sending the whole balance to a single address, you're increasing the priority and reducing transaction size enough that it relays with no fee.