Have you configured the "ip helper-address" statements on the interfaces to allow UDP broadcasts to go across the VPN.
Without these, the Microsoft Browser announcements will fail.
As an example
interface Ethernet0/0
description connected to Private Lan
ip address 192.168.1.1 255.255.255.0
ip helper-address 192.168.2.5
The IP helper-address points to BDC for NT Domain in the remote site.