Hi Justin,
I would also make sure that any other PHP configuration files, and PHP extensions set up during the installation process are checked to ensure that their default encoding is set for UTF-8.
If that doesn't work, my only other thought would be to try switching the language of the interface to Greek, and performing your search there. Have you added Greek as a language in the language menu? If so, I might suggest switching the language of the application interface to Greek, and then trying your search. Note that adding a new language generally requires you to rebuild the search index.
Hope that helps,