i have a flash based nav ... client wants it, don't ask. now ... aside from a sitemap, i'm looking for the users OS ... if i see windows or Mac ... using my php i show the flash header/nav. if i son't see windows or macintosh ... i show the exact same looking area but it 100% HTML ... it looks the same minus the interaction. the site shows a PR zero due to masslinking techniques, it's been clean of this for a long time but no improvement. so before i file a re-inclusion request with google, is what i mentioned above going to be seen as a bad thing? i'm not trying any keyword tricks ... nothing like that ... this is clean.
I don't think this is considered cloaking whatsoever. However, I know a popular method is to simply repost the menu links in the footer.