When the pickins' are slim, it might be time to pick off some less than optimal fruit.

My wife -- who foolishly missed a CC payment last year for two months, plunging her pristine high 7's score down to around 695-715 -- is attempting to rebuild her credit again by grabbing a couple no fee cards with small spends and smaller rewards but which when taken together give you something decent. In her case, we grabbed the 60K AMEX Hilton card and the Citi Hilton 50K card. She can keep them forever to build her credit long term, and 110K Hilton points for 2K in spend is not too shabby either.