SQL Server Certificate
That warning is just checking to see if you've ever backed up your encryptor certificate using T-SQL.  This could put you in situation where the database backup would be unreadable if you were to lose that SQL Server instance for whatever reason. 

No, you don't need a regular backup cycle for the cert. You wouldn't need to back it up after the initial one unless you've lost your copy.

That warning is just checking to see if the pvt_key_last_backup_date IS NULL.

    select pvt_key_last_backup_date, * 
   from master.sys.certificates 
   where name = 'BackupCertifcateName'


Perhaps that backup was taken with a different certificate than the one you've backed up?

You can check to see which Certificate was used with this query:

SELECT 
    c.name as backupCertName,
    key_algorithm,
    encryptor_thumbprint,
    encryptor_type,
    backup_start_date,
    type as backupType
FROM msdb.dbo.backupset bks
JOIN master.sys.certificates c on c.thumbprint = bks.encryptor_thumbprint
WHERE database_name = 'DB_NAME'
AND Encryptor_type = 'CERTIFICATE'
AND type &lt;&gt; 'L'
ORDER BY backup_start_date  DESC