The vpn software is hand-rolled by technogods, and is thus a complete black box to me, and I have no real clue when it comes to debugging problems with it.
It's probably a bad idea at this point (as in, don't change things at random until you know what went wrong), but you could try the other hand-rolled vpn software...
In protocol terms it places fewer requirements on a firewall than udptunnel; it only requires UDP connectivity on one fixed (incoming) port and doesn't need ssh, an account on the firewall machine for peer sites, etc.
I believe it's easier to get working than udptunnel, but I expect I'm very biased. Other users might give you a more useful opinion.
Re: I'm going to regret this...
It's probably a bad idea at this point (as in, don't change things at random until you know what went wrong), but you could try the other hand-rolled vpn software...
In protocol terms it places fewer requirements on a firewall than udptunnel; it only requires UDP connectivity on one fixed (incoming) port and doesn't need ssh, an account on the firewall machine for peer sites, etc.
I believe it's easier to get working than udptunnel, but I expect I'm very biased. Other users might give you a more useful opinion.