1) YP is fighting for their lives to stay relevant. I think that are divested from AT&T.
2) How large of an area do you want to serve. I don't know my New Mexico geography, so I looked up Rio Rancho. Do you get into Albuquerque or is that a "separate" market? If you are serving/marketing to the whole metro area, that is going to be tough to be on the front page...so you may need to pay that much. If you are marketing to a smaller population, $700 is insanely ridiculous for SEO services. One of the things search engines are trying to do is make results more locally relevant...so the bigger your "local" the more companies fighting for that same space.
3) What is your total marketing budget? I wouldn't spend too high a percentage on one thing.
4) (maybe the most important question): Who did your website? A good website is optimized for search engines from the design. There is NO way I'd have YP do my website. I have seen too many crappy ones from them. Find a local designer to do the website for you. DO NOT have your web design tied to hosting or hosting tied to your design. When you hire the design, you want to own it and control it so if something goes south with the contractor you don't want to have to start back a square 1...you should have a functioning site that somebody else can pick right up where it was left off.