Make sure you have a default gateway. Check Diag > Routes, make sure you have a "default" line there. If you don't, then go to System > Routing, edit one of the gateways and mark it default, then save/apply and check it again.
Try to ping out from the firewall by IP address, see if that works.
If you can ping to 8.8.8.8, perhaps set that as a DNS server under System > General Setup and enable forwarding mode in the DNS Resolver.
Also you could try disabling DNSSEC.