I just had the very same problem on a 1 month old Roomba 560. I am cleaning the brushes on a regular (daily) basis, taking care of the yellow rings on both ends. But after running for ~20 seconds to a minute, the dirty brushes message kept coming on. I took everything apart, cleaned it and it still did not work. After some googling, I found this site and thanks to the image posted by Spektator, I noticed that the little yellow end bushing at one end of the brushes can be taken off. It pulled out easy and wow, the space was FULL of cat hair! I did not think that much 'stuff' could be contained in such a small space. Now the Roomba is happy again!
Thanks to Spektator and this site!