I'm having this same problem - as found in the google developer group. I quote what it is a very detailed explanation by Chris Grebeldinger (original author).
"In the documentation:
It recommends testing backup/restore of your application by:
Thanks again to Chris Grebeldinger which kindly answered my reply to his original post in the google android developer group.
How it does work:
What annoys me is that the "steps" as shown on the Google Android documentation which appear to be quite detailed decided to omit what it appears to be a necessary and compulsory steps.
As Chris mentioned on his reply, I hope this helps other people who find the same problem.
After further testing with different devices, it appears that the whole backup/restore process can vary from manufacturer and device. I could test the sample app using Google's document approach i.e. by uninstalling and installing using a nexus 7 - just by a coincidence. So, my advice would be not to expect the same behaviour and consistency during your tests.