You'll see this message when a hard disk's S.M.A.R.T. (Self-Monitoring, Analysis, and Reporting Technology) status begins to report a failure.
Modern disks have a set of tests and benchmarks as part of their S.M.A.R.T. profile and operating systems perform quick tests on them occasionally. When certain tests fall below their specified operating values, this is usually a sign that the disk is getting old and that its performance will likely quickly continue to deteriorate to the point where you suffer data loss or it just packs up and dies.
You can verify this through Disk Utility (sitting in System -> Administration). Find the disk, click SMART Data and you'll see a list of tests. Not all tests are performed automatically so you can manually set it to run a full test cycle but as soon as you see bad sectors or tests that are failing really poorly, the disk is as good as dead.
Obviously data loss is horrible so I can't recommend anything but moving everything off the disk right away. There is nothing to be gained from hanging onto the disk until it pops. It's better to be in control of the situation than have it jump on you when you're not expecting it.
I wouldn't even attempt a low-level format. If it's failing now, it's much more likely to start getting sector corruption in the future. In my mind, it's just not worth the risk.
Note: If it's still under warranty and you send it back, you will almost always (99.999% of times) get a different drive sent back. Diagnosing single drives is much more expensive than just bulk-refitting them. As a result you'll lose all your data in the process so get your data off now.