I think your background actually sounds pretty strong. People get in to top 10 programs from unranked schools all the time, if they have good research skills, and good recommendation letters. Advisor connections help too. Don't discount your undergraduate research, either! Even if it's not quite the right field and it was a long time ago, a history of successful research and conference presentations shows a solid ability to do research, which is the number 1 thing they are looking for. So make sure it shows in your application. The most important things for PhD admissions are research experience and recommendations, and everything else like GRE, GPA, and school name come after.
As for the GRE, buy some prep materials and/or consider taking a test prep class. My feeling is that your GRE scores just need to be high enough to show competence, and above some level the exact score doesn't matter. Not sure what that level is.
It is important to talk to your advisor now about your desires to look at other schools, and tact is really important since his letter is going make you or break you. I would just approach him and say "I wanted to let you know I'm thinking about exploring PhD opportunities at other schools. Are there any schools you think would be a good fit for me?" If you want, perhaps mention that you could continue to work together during your PhD even if you are elsewhere, as many students collaborate with profs at other schools. My guess is that while he may be disappointed, he will understand and want you to succeed. If you wait to talk to him about it though he could feel he misled by you, so do it soon.