Add a machine to a domain on the other side of a VPN connection...

The problem probably is that the computers in the remote office can't "find" the domain because they are on the other side of a routed interface...  You can get around that by putting entries in the HOSTS and LMHOSTS files on the 2 remote computers to point to the resources in the other office...

Let's assume the following (customize for your network)

Domain Controller name: SERVER
Domain mane: MYDOMAIN
Domain Controller IP Address: 192.168.0.100

On the remote PC's add to the HOSTS file the following line:

192.168.0.100    SERVER

In the LMHOSTS file add the following:

192.168.0.100   #PRE   #DOM:MYDOMAIN

Those files can be found in the c:\windows\system32\drivers\etc folder.  Depending on the operating system, you may need an elevated command prompt (if your modifying them from the command prompt) or need to change permissions if your using Windows 7 or Vista.

Once you've added those entries to those files, from a command prompt as an Administrator, type the following command:

nbtstat -R

That will reload the netbios name space and your should now be able to contact the domain to add the machine to it.  Oh, one more thing, you want to make sure that those workstations are pointing to the domain controller as their DNS server, that is requies so that they can find the service records for the Active Directory services (such as Kerberos and LDAP).