Reader is all that is needed to validate signatures. It sounds like you have not established a trust relationship with the signer successfully. In Reader, go to Document > Manage Trusted Identities and then select the Certificates display. Is the signer or the issuer of the signer's certificate listed there? If not, you need to add it. If so, click on it a select Edit Trust... The "Use this certificate as a trusted root" box needs to be checked (Acrobat/Reader 9) or "Signatures and as a trusted root" (Acrobat/Reader 8).
If the desired certificate isn't listed, the easiest way to add it is, from the signature, right click show signature properties, Click Show Certificate. From there, select the cert (or its parent or issuer), then click the Trust tab, then click Add To Trusted Identities. Be sure the trusted root checkbox is set before clicking ok a bunch of times.