Cannot ping B from A until B pings A
Solution 1:
Does sound like a arp problem, if its long spanned vlan over a vpn or similar, you may need to add static arp entries, with an ether address of the local switch.
arp -s <destination address> <mac address> -i <interface to go out via>
And if thats the fix, you will have to add this to command to start up scripts.