Hmm, that's odd. Did you follow every single step each time? If so, I have no other ideas. The original post mentioned that it might be time sensitive - you have to get all the steps done quickly or it might not work. Try doing them faster maybe?
Edit, here are the steps. Note the end of 5 for being "too slow":
1) Make sure phone is fully charged or is plugged into power (it's also is good to be on wi-fi)
2) Settings > Applications > All (tab at top)
3) scroll down and select Google Service Framework, Tap on Clear Data
4) go to system update and update PRL, then update Profile, then update android (aka Samsung Software).
5) if step 4 doesn't result in an update being applied, repeat steps 1 through 4. For some reason I sometimes have to do it twice before it works. It might be whatever step 3 is clearing gets "uncleared" if you're too slow -- not sure.