I am running Fedora 7 with a proxy server software on it called EZproxy.

Ezproxy will send a cookie once a user is authenticated, but for some reason, Fedora will not accept the cookie. I have enabled cookies through FireFox by selecting the Cookie option "Accept cookies from sites" to "Keep until I close Firfox" selected.

Just in case, I have disabled SElinux and the Firewall just for testing (this is test machine so disabling the firewall is not a big security issue)

However, EZproxy indicates that it cannot authenticate and that it is asking for a cookie.

Does anyone know what else I should be looking as far as Fedora or Firefox is concerned to resolve this problem?

I did not understand what this EZproxy is doing. You may use Webdeveloper plugin in firefox and explore the HTTP request / response packets.

Do you mean HTTP cookies?