you need to install a patch for Access 2000 to work against SQL 2000.
I'd just run officeupdate.microsoft.com or make sure you have the
latest SP for office

and you're doing SQL authentication.. right?

I'd give that a shot

The Access 2000 format is the default.  If all users at your company have
Acces 2003, then you can choose the later format.  For your VPN problem,
here are some possibilities:

1- Your local machine has the same address as another machine on the LAN
(VPN) network.

2- You machine has been hacked, is now a zombie and is sending a lot of
scrap, such as spam, over the internet.  This added traffice generates
multiple time-out problems when trying to connecting/doing work with
SQL-Server.

3- There are more than one default gateway/routing addresses that have been
defined for your LAN.  This is not a problem with stateless protocols such
as making a GET request to an HTML page over the internet but will prevent
authentified connections to work properly.

(One way to determine if you are in the third case is by looking at the
number of unencrypted packets received locally by the VPN software when you
are only trying to access the remote SQL-Server (and not doing something
else as dowloading files from a P2P applications): if the number rises
continually, then you are receiving packets from two tunnels (routes or
connections) from your LAN when making a request to the SQL-Server: one
encrypted and the other not encrypted.  As the VPN software will drop any
unencrypted packets once a encrypted tunnel has been etablished, you can see
that this will make no good to your Access connection.  I've been myself in
this situation last year, with exactly the same symptoms as yours but, of
course, I cannot tell you for sure if you are in the same situation or if
this advice is good for you, too.)