This might happen with all Non-English, more special characters but in this case we would use only accented ones (Hungarian characters).
So, to demonstrate the problem: we have product names starting with 'Ké' (such as "Kéztörlő") and with 'Ku' (such as "Kulacs"), and as we know the charater 'é' should appear before character 'u' ('é' comes after regular 'e'), but on the frontend site when we sort products by name, the accented characters are placed after all English characters, so "Kulacs" comes before "Kéztörlő". Also, products starting with 'Á' or 'É' are also placed on the end of the list. However, inside their scope, 'Á' correctly comes before 'É', so there is a correct ordering among them.
And another interesting thing is that on the admin page, under Catalog -> Categories -> Products in Category, the listing is correct, so "Kulacs" comes after "Kéztörlő". From this I suspect that the database is not the place where sorting goes wrong. But then where? And why does it even change between admin and frontend page?