Network cable color coding

Where was this cabling that you checked? Was it inside a patch cable, or on the back of a patch panel with a punch-down? (this is not obviously clear from your question).

If it was on a punch-down, the internal connections of the external blocks to the internal pins is not obvious. Different punch-downs have different wiring requirements, so you'll need to check the actual wiring against the standards that the punch-down has. (These are usually printed on the terminal block itself). There is two standards, T568A and T568B. You need to be consistent with which version you use.

Typically I see older installs with T568A and newer installs with T568B, but there is no hard and fast rule about this. One place I saw T568A on half the connections and T568B on the second half (newer installs).

In that photo you can see the different pinout diagrams on the inside of the terminal block. Some block have it on the side of the block, and others have it on a plastic cover that goes over it.

Based on your update, this is certainly wired incorrectly. I would check the wiring at the wall socket end, and get a contractor in to wire them correctly (try by just cutting the ends off and re-crimping them correctly. You should not need to re-run the cabling unless the cables are physically faulty). Yes, cross-talk can greatly affect transfer speeds. If your workstations are only negotiating 100Mbps, or are negotiating gigabit but only getting 100Mbps equivalent speed, then I would definitely be getting this looked at.