I got everything working, I followed the below steps.
You can install another certificate fairly easily if you want to extend the validity period. It looks like the original problem is that there was something wrong with the server certificate.
A couple things you should know:
1. It isn't necessary to have the client settings configured to validate the server certificate. This is just for better security.
2. In the link I gave before (http://support.microsoft.com/kb/814394), there are some requirements for the server certificate. One of the requirements close to the bottom of the page says "For wireless clients, the Subject Alternative Name (SubjectAltName) extension contains the server's fully qualified domain name (FQDN)." This may be why one of the certificates you installed isn't working.
Load up the certificates mmc snap-in for the Computer account on your DC and look at the certificates in the Personal\Certificates container. Double-click the certificates and then click the Details tab. This displays information about the certificate such as the subject alternative name, the enhanced key usage, and the valid from/to dates.
You can delete certificates here if you aren't using them. You might want to re-issue a certificate and then delete the old one.
To re-issue a certificate, first you should review the template for the certificate. Type certtmpl.msc at a command line (click Start, Run, certtmpl.msc, enter) to open the certificate templates console. If you installed an Enterprise CA then you can create and modify templates. The instructions you used did say to create an Enterprise CA, so you should be able to do this.
Try this:
1. In the Certificate Templates Console, under Template Display Name, find Computer. Right-click it, click Duplicate Template, and then click OK.
2. In Properties of New Template, on the General tab, under Template display name, type a name for your new template. You can use something like Wireless Server Auth. While you are on the General tab, you can also set a validity period. By default it will be 1 year. Change this if you wish, but read this first: http://www.expta.com/2010/08/how-to-create-certificates-with-longer.html - if you try to create a validity period longer than 2 years it won't work without some tweaking.
3. Click the Security tab. Here is where you need to add permission for you to enroll. Click Authenticated Users and place a check in Allow for Enroll.
3a. (Added a step here). Click the Subject Name tab, choose Build from this Active Directory information, and then choose Common name from the drop-down list.
4. Click OK and now you'll see the new certificate at the bottom of the list. There is just one more thing to do now to enable the CA to actually issue this certificate.
5. Close the certificate templates console. Click Start, Run, certsrv.msc, enter. This will open the local Certification Authority console.
6. Click Certificate Templates and have a look at the list. This is all the templates that this CA can currently issue if the user and computer has permission to enroll.
7. Now right-click the Certificate Templates folder, point to New, then click Certificate Template to Issue. Scroll down the list and find the new template you created. The name I suggested was Wireless Server Auth but you might have picked something else. Highlight this template and then click OK. Now you should see that it is added to the list of Certificate Templates.
8. While you are in this console, click on the Issued Certificates container. You should see a list here of all the certificates that this CA has issued. You can also view Pending Requests (for certificates that require approval before being issued) and Failed Requests (there was a problem issuing the cert).
9. Now go back to the local computer certificate console (Start, Run, mmc, enter, File... Add/Remove Snap-in, Certificates, Add, Computer account, Next, Local computer Finish, OK). Right-click the container under Personal\Certificates, point to All Tasks, Request New Certificate, Next, Next. You should now see the Wireless Server Auth certificate. Choose it and click Enroll. At this point you should now see another certificate in the list. You can tell which one is the one you just issued by looking at the details tab and viewing Certificate Template Information.
10. Now go back to PEAP properties in the Network Policy and choose this certificate.
