Strictly speaking, your own certificate is not required for sending encrypted e-mail, only for signed e-mail.
Are your smart card certificates imported on your blackberry?
You can do this from Options>Security>SMIME>Import smart card certs (menu options).
That you see yellow checkmarks would indicate that you do have the certificates though. If you go to the Certificate options where you presumably see this and open a certificate you should be able to see the status of the certificate. It's likely something like a stale status, or unknown chain. If the chain is unknown, you'll want your Root CA certificate. If it's a stale status you'll want to ensure you have LDAP/CRL/OCSP all setup properly.
Some more information regarding the message shown would be nice if anything is available.
Also, presumably the use of a CAC card and e-mail encryption comes from up above in your organization, so your IT dept. should definitely be able to take a look at this for you, always friendly while making you keep company security policies