You say that the switches are on different floors, and you also mentioned patch panel. You also mentioned that you had a Fluke and tested a CAT6 cable that tested fine.
Is the cable running between the floor this same cable or is this a patch cable your are just connecting into the patch panel? What I'm trying to get you to confirm, is that end-to-end (cable, jacks, patch panels, patch cables) are confirmed minimum CAT5e or greater and have been tested with a scanner that certifies it to run at 1Gb. Kinks, severe bends, excessive pulling when installed can cause all kind of issues when pushing the cable to those higher frequencies that a Level IV scanner will reveal.
I have setup many Catalyst switches and they are among the least forgiving when it comes to cabling infrastructure. This is one of the main reasons for connectivity issues at higher speeds because with the degradation of signal on a "problem" cable segment, there will be a problem with the auto-negotiation between the switches as they negotiate what speed they can talk to each other, thus because of the degraded cable, will talk at a lower common denomenator.
That's my opinion at least, and we all have them ;>)