Silly question perhaps but the only times my back ups failed was because My sd card was full. This was something you checked I presume because you're not a silly puppy like me ?
Also the kies thing baffles me as if your phone is rooted it shouldnt recognise it. Former S2 owner myself and it applied there too. I suspect a dodgy flash in the first place.