Actually the service was suspended about a year ago its been a while since K2 were at BHX.
I did see one of their TU-154s when I was at the airport to see the first PK flight. That day was 16/4/2000, not long after the Sunday afternoon service was suspended.
I'm certain the A320 flew nonstop to Bishkek (FRU). However the TU-154s may have routed with a stop enroute. Some of the cities included may have been Kiev, Minsk and Kishinev. Sorry, my memory of the flight routing is a bit vague.
In the last 5 years there have been a number of airlines to BHX from the Central Asia (CIS) region. The first to do so was Tajikistan International who flew to Dushanbe and continued to Delhi with a leased TriStar. They where followed by Turkmenistan who recently went daily and have rights to fly ASB-BHX-YYZ/JFK. In March 2000 Uzbekistan flew Thursday and Friday 757 service, continued onwards from Tashkent to Amritsar. This route was recently suspended. Also Kazakhstan served Almaty with Tupolevs for a short period.
Oops, too much information!