Try recording your fingerprint many times and move it around a lot.I have a amazon cheapie as well. It works like 25% of the time, I have to press my finger in a certain position to get it to work. I did the update yes, I believe there's another update on the way that some users already have (I think North America)
Some people say they need to touch their nose to get some "oil" on their fingerprints if they have very dry hands...!