I actually did send bitcoins (with no fee) to another wallet on a smartphone, but while the trasaction cleared the bitcoins from my pc wallet, it did not appear on my smartphone even after several minutes. I then recovered a backup and sent the same bitcoins to another address (MtGox) this time with a fee and they did move to MtGox. I suppose I double-spent them, but it worked.
Your client only sent the transaction to one other client, to better hide the origin point of the transaction. That client refused to relay the transaction because you didn't include a fee. So that transaction never got anywhere. Had you left the client running, it would likely have eventually sent the transaction to a node willing to relay it.
Once a transaction gets out broadly, the network will not accept a conflicting transaction. You'd need a conspiring miner to get the conflicting transaction into a block.
OK, so had I left the client running, it would have completed the transaction eventually and then would show up on my smartphone? Still, it concerned me that the bitcoin amount was debited from my client, but not immediately credited on my smartphone client.