Are there any PhD scholarships for 3.5 CGPAs? I have recently thought of pursuing my PhD. I have managed to make a research proposal. I have done part time MS (i.e. struggle after working hours) with thesis and managed 3.5 CGPA (85%) out of 4.0 and I managed to have one publication in an IEEE conference. 

While corresponding to supervisors, I feel some of them like my proposal but it always comes down to availability of a scholarship. For example, I started a correspondence with one supervisor in New Zealand who was willing to supervise me but he won't give me go ahead for university admission because I haven't secured any funding and he thinks that I have no chance to win any university scholarship with this GPA. I told him that my average is 85% and I have over 5 years of relevant work experience. I asked him the minimum % to win a scholarship, to which he replied "100%". He says work experience is never a major factor for scholarship award.

Now as it seems that my GPA is a barrier to even have an admission in a university let alone win a scholarship as most of them don't want to waste their time on a candidate who won't be able to fund himself.

Situation for me looks bleak. Can't bring back the past to work hard and get better CGPA or should I start thinking of doing MS again? As for now it seems that PhD scholarships are only for the applicants with Gold medals and 4.0/4.0. Any ray of hope? Is there any chance that I'll be able to have a scholarship?
I think a 3.5GPA for graduate school is not bad at all. Though it really depends on where you are applying from. International applicants usually are scrutinized further, especially due to the shear number of international applicants and fewer funding sources for non citizens. I think it would be best to talk with professors from your university or alumni who have pursued graduate school about locating funding and which universities/programs will already have funds for students.

The other thing is the professor may not actually be that interested in you. Professors often will take almost anyone if they are free, but once they have to use their research funds, the standards increase.