When deploying an AP you should take into account both coverage and capacity but in the other hand you should be aware of the medium, for example how high the SNR is.
Some other factors to take care of are:
Other nearby Wi-Fi networks , mainly if you are using 2.4 GHz band
Any other device that uses the same frequencie, Again mainly in 2.4 GHz band
You can always use a protocol analyzer and look for high retransmissions, hidden node problems. among others.
Yeah, we went down that road and ended up relocating the APs...we had issues with interference and building materials (new construction). We're confident that our wireless is working well now. We also used Metageek's Wi-Spy spectrum analyzer - very nifty tool.