Whenever a major vulnerability is discovered, the natural inclination is to panic –what if data is being compromised? What if hackers are attacking my servers right now!? Nevertheless, anybody with experience can remember how, under pressure, other major issues resulted. Process exists for a reason, and serious vulnerabilities are the ideal candidates for a good shakeup of process (your organization *does* have a planned process to deal with critical vulnerabilities, we hope!).
The old standby, system uptime, along with internal business best practices regarding risk assessment, tactics and good strategy remain the stalwarts to guide your response to Heartbleed. First, do you understand the problem? (If you think you just need to upgrade to the latest OpenSSL, then again, some more time should be spent in understanding the issue). Then, once you have identified the servers affected in your organization, hopefully by looking at a master inventory or using tools to get you updated information, you can initiate systematic remediation in a well-considered fashion.
Yes, at some point you might want to change passwords, change encryption keys, perhaps even invalidate a few certificates –if you have (as you should) plans to execute this in a planned basis every year or two, accelerating the schedule is probably a good idea. But, when you do this, you need to follow best practices and protect encryption keys –if, for example, you begin changing everything on the fly, sending passwords and certificate requests over email, placing them in any USB you find, sending a new employee not properly vetted to update many servers –no matter how well intentioned, you might end up in a less secure place, or worse, with a broken system.
So, follow good process and carry on.