I think this may be a bug in Summer 13 but I'll take a shot here for some troubleshooting ideas.
Have a Flow as part of managed package that has a Dynamic Choice lookup to Contact object. When type in James should do "all names that contain James". Package has worked fine until earlier this week, first new release after Summer '13. Works fine in Developer org. After we install in customer org the Dynamic Choice is blank when it shouldn't be. Happens under all licenses, including Sys Admin.
Sharing settings are Public/Read Write on Contact. Only 1 record type on Contact which all records have and all profiles have access to. All Contacts have Accounts (so none private). Tried changing owners on Contact back and forth...nothing.
I don't see how to use the Debug logs in this case as the SOQL is inside the Flow, but maybe I'm missing a debug option to see what it's pulling back when Flow executes?