A test confirms that the server sends all intermediate certificates, so there shouldn't be a problem with Firefox.

• http://www.networking4all.com/en/support/tools/site+check/

Possible causes of such errors are that the system click is set to the wrong date and time or that Firefox has stored in the past a certificate that has now expired.

Visitors that have the problem can try to remove the stored intermediate certificates that are used with that connection.

• Tools > Options > Advanced > Encryption: Certificates > View Certificates : Authorities

Stored intermediate certificates show as "Software Security device" and the build-in root certificates show as "Builtin Object Token".
Don't remove the latter.

Rename the file cert8.db to cert8.db.old in the Firefox Profile Folder to remove all intermediate certificates that Firefox has stored by visiting secure websites.
If that helped to solve the problem then you can remove the renamed file cert8.db.old unless you have user certificates that you may want to export first and import them in the new file.
Otherwise you can restore the certificates by renaming (copying) the file back to cert8.db
Firefox will automatically store new intermediate certificates when you visit websites that send them.

Thanks for the response. It looks like somehow the certificate chain had broken somehow, so while FF was seeing the certificate and knew it was from Network Solutions it was unable to complete the chain to a root CA, reapplying the chain of certs on our Apache server was able to fix the problem.