> Try n/b/g in 20Mhz or N only in 20Mhz?
N/G/B or N/G if an option. 40Mhz channel width is not good in 2.4Ghz range, it should auto fallback, but I'd suggest disabling it anyway as a rule in congested environments . You may also improve performance by not supporting B, just support G and N - or test each case.
> As far as manually modifying the channel, what about AP's bleeding through the floor?
Yes, it is difficult in a 3-dimensional space to have 3 non-overlapping 2.4Ghz channels. The only way to deal with that is to consider radio lobe patterns, antenna positioning, building construction floor attenuation, radio strength, and frequency selection. It's all about minimising overlapping channels, and if they do have to overlap, then have them do so in a non-client area. In complex multistory buildings, it is very difficult to get right in the 2.4Ghz range, and relying on auto-channel selection won't work.
The only real way to tell what frequency overlapping is a problem is to site visit and survey, my suggestion is at least WiSpy tool and InSSIDer, or better.
> I would want the next floor up to be on a different channel than the floor below correct?
What some people do is alternate APs on each level, so there are never APs on every level at the same position. Example, Level 1 and 3 has similar positions, and Level 2 and 4 have their positions dissimilar to 1 and 3. Sometimes you need to use external antennas to cover an area correctly and not bleed into other areas.
> A site survey was not done. I tried pushing for one 5 years ago because of the building and coverage requirements.
It is still worth having someone professional to review your site. Doing it yourself can cost more, a professional has expert knowledge and tools, and should be able to do your environment in a matter of hours.
> As far as the N clients not connecting, I have a single access point in our office and when I set my wifi card to n/b/g, my speeds are horribly slow. When I change it to b/g it works great.
This may be unrelated to radio frequency spectrum and interference. It could be more of a OS, patch level, driver, firmware and/or chipset issue on either the client or the AP. Try and reproduce the problem with a different N client chipset.