Don is absolutely correct: the problem is that Picasa caches the EXIF orientation information, and doesn't pick up changes made by another application.

However, there IS a need to use an external application for persistent, save-back-to-file rotation, as not all viewers out there (including, for instance, the HD photo-viewing application for Tivos), respect the orientation flag. Doing this in Picasa is - as far as I can tell - not an option, as Picasa won't even SHOW you which images have been auto-rotated.
In other words: to ensure correct display in all viewers, you need to rotate persistently using another application, i.e. rotate and save back the rotated version.

To work around the current problem in Picasa after having persistently rotated photos elsewhere, simply rotate them *again* in Picasa so that they display correctly there - at that point, they will display correctly everywhere.

Let's hope this problem is fixed in Picasa soon.