I tried that, it failed with following msg:
restorecon set context /var/spool/squid->system_u:object_r:squid_cache_t failed:'Permission denied'
BTW, I also tried that command on /tmp/squid without mount shm to it (just to test the result of it...), and the command succeeded, but when I point the cache dir to /tmp/squid, I still get the same error...
That's because the policy for /tmp is not the same as for /var/spool/squid so restorecon will set different contexts for the two directories.
I think your best bet now is to follow Rahul's advice; update all selinux-related packages to the latest ones available, relabel the machine and if it still doesn't work, try the fedora-selinux list.
Paul.