Java And Cookies Not Enabled: Unable to view site!!

I have had SEVERAL customer complaints that they cannot get into our site, because of needing to enable JavaScript and Cookies.

I have looked into this problem and discovered that even with Java/Cookies enabled the error message still seems to appear. I have not been able to narrow it down to browser or platform (as it happens on multiple browsers and on both mac and pc platforms) 

I have taken a screen shot of the preferences in ie here: http://screencast.com/t/PxN5TF9Y

Also, here is the error message that pops up: http://www.layerxperts.com/requires_cookies 

Any idea on what might be causing this? Has anyone else experienced this?