Joe,

Anecdotal evidence suggests that failing a CIA pre-employment polygraph interrogation is not necessarily a bar to holding a security clearance with another federal agency.

Suppose at your CIA pre-employment polygraph seance the polygrapher divines that you have been deceptive. As I understand it, your application for employment is terminated then and there (unless you are invited to have a second polygraph reading done). That being the case, I don't think it would be incumbent upon you to report that you were denied a security clearance by the CIA; rather, you would have merely been denied a job, since the Agency would never have actively sought a security clearance for you.

If, on the other hand, you're working for a CIA contractor, and the contractor is seeking a security clearance for you that is conditioned upon your passing a polygraph "test," then indeed, you might have to report that you have in the past been denied a security clearance.

(If anyone reading this knows what I've written here to be wrong or in need of qualification/clarification, please don't hesitate to post.)