I do hope the OP updates us on the FOIA request and is able to find out what the denial is based on. I went through the Nexus process which is the same except I also had to be interviewed by a Canadian agent and even though I had only traveled overseas once in the last 10 years had no problem.
You may be tempted to give up fighting the faceless bureaucracy but I hope you keep pounding away until you get your clearance. Good luck and keep us informed.