CiviCRM calims group already exists while using unique names

My problem is that when adding groups and using unique names some of the groups fail to save with the message "Group already exists".

Version:
CiviCRM 3.4.1 integrated with Drupal 6.22.
MySQL - 5.0.87-percona-highperf-log

CiviCRM tables collation is utf8_unicode_ci
Other Drupal tables collation is utf8_unicode_ci or cp1251_general_ci (Cyrillic)

Try the following strings (lat prefix + cyrillic text):
Plugable: Големи магазини за техника
Plugable: Големи магазини за PC
Plugable: Лаптоп магазини

1) and 2) were added successfully. 3) failed.

More info:
Removing the common prefix and making these 3 groups subgroups of a common parent worked for me.

IRC log:
(17,58,03) atodorov: hi guys, I have an issue adding new groups to CiviCRM. it says that group already exists but it doesn't. Could it be that I'm writing in cyrillic?
(17,59,05) atodorov: I managed to add 2 groups with name such as: PREFIX_IN_EN: ... text in cyrillic ... and it failed when adding the 3rd one
(17,59,06) michau: atodorov: Shouldn't be
(17,59,13) atodorov: michau: ^^^
(17,59,32) michau: atodorov: What are the names of those two groups?
(17,59,46) michau: atodorov: (I can read cyrillic, so paste them as they are)
(18,00,35) atodorov: michau: Plugable: Големи магазини за техника (worked), Plugable: Големи магазини за PC (worked), Plugable: Лаптоп магазини (fails)
(18,01,09) atodorov: as you can see they have a common prefix but the full name is unique
(18,01,28) atodorov: civicrm still claims that the last group name already exists
(18,03,04) michau: atodorov: Hm, strange
(18,03,30) michau: atodorov: I would expect first two not to play nicely together
(18,04,03) atodorov: michau: why not? (unless only first characters are compared)
(18,04,24) michau: atodorov: That was my suspicion
(18,04,35) michau: atodorov: But doesn't seem to be a case
(18,05,38) michau: atodorov: I could reproduce it on my local sandbox, so there is an issue
(18,06,22) michau: atodorov: Can you file an issue here: issues.civicrm.org, giving description of the problem, steps to reproduce and above strings?