One of the more common scenarios where CF gets into a broken state is:
1) create new S3 bucket + something else (e.g. some Elastic Beanstalk env update)
2) something else fails, causing rollback
3) S3 bucket already contained data (e.g. your failed Elastic Beanstalk env update caused it to write data)
4) CF refuses to destroy the S3 bucket, entering a "rollback failed" state
In this cause, manually wiping the S3 bucket works well enough. But generally, it appears that CF works kind of when the updates you're making are really small, incremental updates.
Sometimes it gets totally corrupted and you need to nuke stuff, per your advice. This automatically leads me to the following suggestion: leave mission-critical data out of CloudFormation. Specifically, stuff like RDS databases which you absolutely never ever want to have destroyed: just provide the endpoint as an input to your CF template.