I am using my M1001 (US version, latest firmware) with WPA to an Apple Airport Extreme router with no problems, and have previously used it successfully with WPA with a DLink DGL-4300 too.
I don't know what to suggest for you if it is working with everything else identical (same channel, same other wireless settings, nothing funny like MAC filtering enabled on the router, etc) but the wireless set to WEP. All I can think of, and I'm sure you'd have tried this, is to check the upper-lower caseness of the WPA key is right.
I don't know anything about Speedtouch routers at all. If it works well as a router (ie whatever you need to talk to your ISP, plus it has good operation from its wired ethernet ports) and you don't want an overall change, could you get (just) a wireless access point device, connect to the Speedtouch and set it (the new wireless access point) to "bridge mode" (so it doesn't try to also be a router, DHCP server, NAT, etc). That would give you an all-new, all-different wireless environment but not change anything else you already had working properly (at the expense and added complexity of having two networking devices rather than one).
p.s. I actually have three wireless/router thingies at home; a DLink DGL-4300 (gigabit wireless router) which is connected to my cable modem, but has its wireless turned off, and TWO Apple Airport Extremes, both set to bridge mode - one for a B+G wireless network (which the Soundbridge and my work Windows laptop and an older Mac connect to) and one for N (on 5GHz, which the other Macs connect to).