Okay- here's an update to this
http://forums.androidcentral.com/samsung-galaxy-s4/280058-gallery-sorting-albums-date.html#post2868487...i know you're looking more at a picasa/google+ fix, but maybe this will offer some insight to sorting...and offer some help to someone else that has my issue with the gallery sorting.
Since my gallery went screwy after upgrading my sdcard, I have come to discover that windows automatically stamps a "date created" time any time a file is copied. When you copy these to your s4, it changes the order because of when they created actually now reflects the time the file was copied ( I won't get into the technical aspects, but trying to keep it simple).
So, point is - I believe the sort is by the created time, not necessarily filename.
I used this bulk renamer
Introduction - Bulk Rename Utility and it allowed me to change ONLY the exif data for "date created"
(Drag and drop files, highlight them all, select Options > Extract > Exif data, then from the Options > Timestamp > select "Taken" for each > "OK" , then "Rename" at bottom right).
This allows the "date taken" to become the created date, if a date taken is present.
The next step is to use a variant of the lesser-known windows included utility "Robocopy" . I used RichCopy from Joshua Hoffman- a
free Utility: RichCopy, an Advanced Alternative to RoboCopy. This basically copies the files from one place to another keeping the timestamps in place.
The only problem I found with this is that not all pics I had were timestamped with the taken time, so some I'll have to adjust based upon the filename. Those pictures were still visible in the time nearest the "creation" or time copied.
(if the files are initially copied OFF a card with RichCopy, there would be no need to rename and RichCopy could be used to transfer to another card without changes in sorting)....
Not sure at what point you uploaded your files to picasa/google+ in the phone switch, but I'm thinking the date created has something do with your issue as well. I'm not a google+/picasa person, so I can't offer much more. I Hope that helps.
EDIT: 1 more thing- have you tried to go sort your pics in picasa (web) then on your phone, clear the gallery app cache and try to access again from your phone and see if it "re-sorts" for you?