Since you posted this to the SQL Server 2005 section, I am guessing that you are trying to restore a 2008 backup on to a 2005 server, which is impossible.

But assuming that you are restoring to a 2008 server, I wonder if trying to restore the backup without giving it any input for the certificate will give you a hint as to what certificate is required.

Sorry, that's about how much I can help on this.