Ensure that authentication is disabled (via NWAdmin32). In addition, are you doing any type of NAT via the BorderManager solution? If not, you may need to implement your NAT rule to convert your internal networks to a public (Many to One).

Novell assumes that your BorderManager system is directly connected to the Internet and requires NAT or some form of address translation.

I know this was asked above, but do you have Proxy/Cache enabled as well or just the firewall component? Have you validated that your ALLOW rules are properly defined? Can you PING or traceroute from the Netware server that's hosting BorderManager (to the Internet)?