Have you tried entering the access points manually (details here)? It might also be worth checking the frequencies the device operates on. Vodafone are moving their 3G service from 2100mhz, which is generally supported, to 900mhz. A lot of imported devices work on 850mhz.
