OK, let`s leave the bears and the Red Square in peace.
The bilateral relations between Pakistan and Russia can not be improved immediately `cause of the couple of reasons. First one is a miserable heritage of the Cold War. The two countries were on the different sides of the frontline, and sometimes it turned very sensitive for the then USSR, esp. in 80-ies, you know. It`s not so easy to overcome all this in a couple of years. Furthermore, the USSR had established the relations of strategic partnership with India – and Russia didn`t learn yet how to make friends with both.
And BTW, nowadays the Russian Ministry of Foreign Affairs seems to be unaware that not all the Pakistani nationals are 100% al-Qaeda members and the Ministry of Home Affairs wants to make sure they will not go to Chechnya.
As for dual nationality treaty, Russia has one with Tajikistan only, the only country from CIS, what to say about foreign countries.