Edit: In the years that have passed since I first put a Sugru on my car key I've learned a few things:
#1 Make sure that the key is as clean as possible before applying the Sugru (no oils, even from your hands). If you used soapy water to clean the key, also make sure it is completely dry (soapy water inhibits bonding, which can be useful, but not in this instance.)
#2 Wrapping sugru all the way around the key is not necessary. The edge areas are thinner and take the most wear, just omit that part and use your precious sugru for something else.
#3 Choose your pattern wisely. A good pattern gives the key some character. Wire mesh works well, just dampen it with soapy water first, or your sugru may decide it likes sticking to the mesh better.