Factory reset corrected the issue for me.
One other detail in case it helps - when it was not working I could browse the store but at the point where I actually tried to purchase something, I would get the error as well.
Thanks everyone for the help and comments.
