Which is more credible: headhunter or referral?

I am in a position to apply to a competitor either through a personal referral (from an ex-colleague who very recently moved there) or through a headhunter.

Which do you think would lend my application more credibility?

Both are good routes to secure a first interview; after that, you're on your own in most cases.

All things being equal, I'd go via the referral route -- it lets your friend put in a good word for you, potentially earns your friend a bounty, and saves the company the recruiter's fee.

Either will be beneficial - the referral will benefit your friend, should you be appointed, but the headhunter will be able to coach you through the process, get feedback for you, and put your case to the firm better than most. A good headhunter is trusted by their clients, whom often look to them for advice and guidance in the hiring process.