I had the _same_ problem a couple of weeks ago with my new Audrey. Best as I could figure, the modem configuration with my un-updated Audrey was incompatible with the new modems in my ISPs pool. Recall that Audrey is circa 2000 -- maybe they installed some odd 56k negotiation protocol. I dunno.
The solution: use broadband, or the CF method. Once I connected via ethernet, updates happened directly. I can't really connect Audrey to my work network, so my work-around was to install WinGate on a PC, and I used it as my uplink (via the PC's ehternet card), to my ISP. Slow, but it worked. The trick is in setting the gateway/PC/whatever to use the 18.104.22.168 DNS. Oh, and set Audrey to pick up her IP number via DHCP from the PC.
This probably sounds a bit complicated, but WinGate is really pretty straight-forward to set up.
Hope this helps.