I would not characterize the quoted language as a non-compete provision. Instead, it appears to be a non-poaching provision, i.e., you will not solicit the company's employees or consultants to act as employees of or consultants to any other business. In my experience, this type of provision generally is enforceable.
However, based on the facts that you have provided, it appears that you may not violate that provision. In working on the new startup, you apparently will not be "solicit[ing] the employment or consultancy" of your co-worker - you will be soliciting him to be a co-founder.
Furthermore, the point of such a provision is to protect the employer against your poaching personnel you have met through the employer. The fact that you know your co-worker from before the employment relationship is significant.
That said, you still need to be careful. Neither of you should use any of the employer's trade secrets in your new venture, and you should not do any work for the new venture on the employer's time or using the employer's facilities or equipment. You will be in a much safer position if you new venture is in a different line of business from the employer's.
You should discuss this matter in detail with a qualified lawyer, who will be able to provide more-specific guidance based on the details of your situation.
Disclaimer: This information does not constitute legal advice and does not establish an attorney-client relationship.