Just got lil sis a fire phone, also 3.6.8 unlocked 32GB version. Followed the instructions and worked like a charm.
The only thing that gave an error was her Snapchat which said we needed to update Google Play Services... but after a few minutes, we tried again and it just worked.
Thanks OP for the post!!