As others have already pointed out, your phone can't play the part of a USB host, which means that it can't talk to the Arduino in the same way that your computer can. However, there may be other options.
The easiest is to use Bluetooth- that should be doable, though adding Bluetooth to your Arduino will cost you.
You could also look into buying another Windows Mobile or Linux PDA. But even then, you might be out of luck, without the needed USB drivers for the FTDI chip.
You can also get Bluetooth to Serial adapters
- you'd pair your phone with the adapter, and the adapter would talk to the Arduino over RS-232 (not USB).
Either way, you'll probably end up spending $100-150.
I wouldn't cross my fingers, but the docking connection of some WinMo devices support a serial connection which is made available by either hacking your own cable, or an adapter you can buy.