What is a Gateway Game?
BGG has this definition in their glossary:


  A game with simple rules that is easy to teach to non-gamers in order to attract new players into boardgaming as a hobby.


Usually people will say that a Gateway Game must have at least these qualities:


Simple (so you can explain the rules to them quickly).
Fun (fun games will attract repeat plays).
Short (short hits can be played again, misses gives you time to play something else).


The real problem with this definition is that the focus is on the game, and not the goal. If your goal is to attract new players to boardgaming as a hobby, the focus should be on the player. There is no silver bullet with a Gateway Game. The game needs to match the player that you are trying to convert. If you know the new player or can get to know them, you can make better decisions about what games they might be interested in. Speaking in just generalities though:

Are you trying to convert a brand new player who has never played any games?

This kind of player doesn't have any background in any sort of game mechanics. It would be best to focus on a game that has only one or a couple game mechanics so that they don't have to learn too many new things all at once. For Sale/No Thanks have just a bidding mechanic. Can't Stop has a push your luck mechanic. Blokus has an area control mechanic. Cash n' Guns has a hidden selection mechanic. The shorter the game, the better, since you can try many different games until you find one that clicks. Then stick with that game for a while until that player becomes comfortable with the game mechanics and understands that strategies in the game. 

Are you trying to convert a Monopoly, Risk, Trivial Pursuit, kids board game player?

Nothing wrong with suggesting something that might be already familiar. Settlers of Catan has pieces like houses and hotels, and resources (goods instead of cash) are collected based upon what players roll. If they like Risk, there is Risk Legacy, and for Trivia buffs there is Wits and Wagers. 

Are you trying to convert a Party Game player?

Games with lots of player interaction, or cooperative in nature, since they focus on the social aspect of games. Forbidden Island/Pandemic

Are you trying to convert a Chess, Go, Bridge, Poker, or other classic game player?

This person is already a gamer, so you are half way there. They know how to play by the rules and they probably have a good grasp on probability or board position. You probably want to focus on a games that have less luck, and more skill. 

Are you trying to convert a MtG/Yugioh/Pokemon/CCG player?

This person probably already is a gamer by most people's definition. If your goal is to open their mind up to the rest of the board gaming world, you might want to focus on card games so that they are playing a familiar game, Dominion/Resident Evil: the Deck Building Game. Nothing wrong with stretching out to something completely different though. Something themed and less abstract might be more to their liking Gears of War/Shadows over Camelot/Battlestar Galactica.

As to the question, why or why not are certain games are considered gateway games, it usually comes down to not meeting one of the criteria above.


Monopoly: Isn't fun. Players have very few interesting decisions to make that will have any impact on the outcome of the game.
Race for the Galaxy: Isn't simple. I think that mostly it is the iconography that trips everyone up here. The rules themselves are fairly simple to explain (choose an action for the turn, all players perform all actions with bonuses for selecting that action, pay cards to play cards unless military, repeat), but the total number of icons and choices per turn is probably overwhelming for most players.
Spades: Not a Hobby/Designer Game. Most "gamers" do not consider classic games like Chess, Checkers, Go, Hearts, Poker, etc. to be hobby games. Teaching someone to play these types of games will not usually get them any closer to being interested in playing designer games that you would find in your friendly local gaming store. 
Settlers of Catan: A Gateway Game. One of the quintessential gateway games.  Simple rules (roll dice, distribute goods, trade/build, repeat), fun to play, somewhat short (1-1.5 hours) if you use the City/Settlement starting rule. A little bit for every type of player, lots of player interaction through trading, a screw you over mechanic, some luck so the first game isn't a complete blowout, limited options per turn so tactical decisions are easier, and clear VP point system so you know how well you are doing (mini goals).
Ticket to Ride: A Gateway Game. Simple rules (play sets of colored cars, draw cards, link cities to complete tickets), fun game play, and relatively short duration. 


You are not going to find a definitive definition of what is or isn't a Gateway Game. The idea behind it though is to find a game (theme, mechanic) that the new gamer might be interested in so that they become interested in the wealth of games that are available in the hobby.