These are the results of additional investigation: 1. When using bugzilla3 Debian package, bug search by product name with Cyrillic characters does not work at all - no matter with PostgreSQL or MySQL backend. This means that the problem is not limited to PostgreSQL backend.
2. Bugzilla 3.2.3 (downloaded from www.bugzilla.org) works fine. No problems at all and pretty nice localization.