IT Certifications Recommendations

I am a Senior Developer with a very large government contractor - primarily developing web-based applications in PHP and Python.

I was hired for this position in November 08 and started in February 09, after my separation from the US Air Force. At the time of hiring, it was never mentioned that a valid permanent IT certification was a requirement for the position.

Now, I am being told I need to get a Cert, and quickly. My company will reimburse me the cost of the test (not study materials), if I pass.

So, looking for two things:

1) Is this right? Really, there isn't much I can do about it but I feel as if I am getting screwed here somehow. If it was a requirement for the position you'd think I would have been told before now.

2) Any recommendations on a certification to aim for? The logical choice is Zend Certified Engineer but I have heard it is fairly difficult. Plus, it's a certification I actually do want to work towards and get, something I want to do for myself on my own time. I don't have the time in this scenario to do that so I am leaning towards something easier just to get the requirement out of the way. Maybe A+ - I'm fairly certain a blind monkey can pass that.

Ideas?