As per my understanding from you message, your coins are still in your wallet.
I wonder how it will be lost if the payment has not been transmitted.
Try to import your private key to a qt wallet and check your balance.
If balance is not reflecting with the missing coins, do the same thing as I said above.
Get your private key from you android wallet and import it to qt wallet before you re-sync you wallet as said above.
Always remember to take backup of wallet.dat and your private keys before doing anything.