IMHO I would try to get your utilization down between 1 - 9% (if you can). I think this would boost up your score some, which could not hurt. I would then send a recon fax to them and request that they pull a new CR (since they will use the old one for 60 to 90 days). In the recon fax I would explain the late payments for Verizon and point out how you have been perfect on payments the last 2 years.
Also, if you have opened a lot of new accounts recently, then I would explain this. Creditors get a little nervous seeing so many new accounts.
Now let me say that if you cannot get the utilization down under 10% in the next month, then I still would send a recon fax to them. When I signed up to their Credit Union, I thought they were very easy to get a CC through. However, I have learned that they are not as easy to get as I thought, or they might have just tightened up their lending policies from what they used to be. I guess what I am saying is that you should not worry about the first denial. I was denied at first, and my first recon was denied. However, 30 days later I reapplied and they gave me a CC.
Hope it helps. Your score is fairly close to what they require. I think if you can just boost it a little by lowering your util. %, then your in. Good luck.