I've been working recently with some Microsoft Services and their customers who are changing the SharePoint STS token signing certificate.  We are doing this as part of the set of steps required to set up the SharePoint Hybrid features for integrating search and BCS between on premises SharePoint farms and Office 365.  I've had a couple of these folks get a little concerned because after making this change they had a seemingly random scattering of people that were unable to authenticate into SharePoint afterwards.  The answer as it turns out was just that those users still had a valid fedauth cookie from a previous authentication into SharePoint and that cookie became invalid when the STS token signing certificate was changed.  So just in case, here are a couple of things to remember before you undertake this operation:

• You can always back up the SharePoint STS token signing certificate before you change it.  You can use the PowerShell I posted about here to export the certificate:  http://blogs.technet.com/b/speschka/archive/2011/12/21/some-easy-powershell-to-export-the-token-signing-certificate-from-sharepoint-2010.aspx.  Never hurts to have that stored away some way for a rainy day until you've done a complete check of your services.  NOTE:  the link above does not include exporting the private key, which you will need to do as well if you want to reuse that cert in the future.  You can modify the PowerShell to get the private key or you can just export it out the Certificates MMC snap in.
• If after you change it and you have some users who are unable to log in, you can have them a) delete their cookies (which most users are loathe to do, including me), or b) have them use an In Private session to access SharePoint.  Their fedauth cookie is only good for as long as you configured your Identity Provider to make it, so in most cases the cookie expires in a few hours.  That makes this work around only temporary until that cookie expires then you should be good to go again.