Does the firewall have Internet connectivity and working DNS?
Check System > Routing, make sure you have a gateway set as default
Check Diagnostics > Routes, make sure the default gateway is shown there
Check System > General, make sure that you either have DNS servers set there or you have the DNS resolver setup in non-forwarding mode, with Disable DNS Fowarder unchecked.
Try to ping an Internet site from Diagnostics > Ping
Try to resolve an Internet site hostname from Diagnostics > DNS Lookup