Hi op I have been in your shoes. I even offered with some apartments to pay the whole 6 months lease or 12 month lease in full upfront and got turned down! What I have found is that large apartment complexes that are corporate owned are generally very rigid and it is either a yes or no based on their criteria with no flexibility. To have success try smaller apartments or condos that are owned by a private party looking to rent. Also to not waste a lot of time and paperwork and inquires, just ask them upfront what there criteria is and also make copies of you and your girlfriends credit reports to show them up front.
The shopping around is always a bit of pain, but landlords and apartments criteria vary widely so while one may say no the next one may love to have you. Also craigslist is a good apartment hunting resource and many times in their ads they will list the credit criteria up front.
Dont be embarrassed. Many people have had this happen including me. Hang in there and keep looking and you will find a good place.
Starting Scores: 9/19/2012 EQ 613 / TU 526 / EX 543
Current Scores: EQ 716 TU 724 EX 724 Goal Scores: 700