It seems wicd doesn't automagically use the tethered interface, unlike GNOME's network manager.
So to get it to work, first we need to find out the name of the tethered interface (i.e. you need to have the phone connected and tethering enabled at this point already). It should be something like usb0. To find this out you would normally use ifconfig to get a list of the network interfaces... but Arch Linux has deprecated the net-tools package, which contained ifconfig amongst other tools. There's a solution though: use
which will show you pretty much the same information (you might need to prepend sudo to the command).
Once you know what the interface name is, open WiCD, go to Preferences, then the "General settings" tab, and finally make sure the entry for "wired interface" contains the name of the tethered interface you just found out (i.e. usb0). I have also ticked the "Always show wired interface" and "Always switch to a wired connection when available". Finally press OK and hopefully it should automatically connect with tethering.
This evidently isn't an optimal solution --ideally I'd like WiCD to find these things by itself! But it should be OK as a temporary fix until we set up a proper home network. Meanwhile, hooray for tethering!