It's funny how this comes up often. Even though Kleenex is by and far the most popular brand here in Australia, I don't ever recall anyone ever saying something like "pass me a Kleenex". Maybe it's our penchant for either shortening things (afternoon becomes arvo) or adding synthesising suffixes for name (David is always Davo, McDonald's are Maccas) that Kleenex doesn't work for us.