Python rock paper scissors
The biggest problem with this code is that you are using functions as glorified GOTO labels, when choice() is called from within choice, when choice() is called from play, and when choice() is called initially.  If you hit CtrlC after a few rounds, you'll see that the call stack is inappropriately deep.  The remedy is to use functions, return values, and loops properly.

The other change I would suggest is removing the redundancy between the choices list and the win_table.

import random

MOVES = {
    'rock': {'rock':'It was a Tie', 'paper':'You Lose', 'scissors':'You Win'},
    'paper': {'rock':'You Win', 'paper':'It was a Tie', 'scissors':'You Lose'},
    'scissors': {'rock':'You Lose', 'paper':'You Win', 'scissors':'It was a Tie'},
}

def choices():
    """Produce a tuple of the player's choice and the computer's choice."""
    while True:
        player_choice = raw_input('Choose rock, paper or scissors: ')
        if player_choice.lower() in MOVES:
            computer_choice = random.choice(MOVES.keys())
            return player_choice, computer_choice

def reveal(p_choice, c_choice):
    """Print both players' choices and the result of the game."""
    print 'Computer chose', c_choice
    print MOVES[p_choice][c_choice]

def play():
    """Play a round of rock-paper-scissors, then repeat if desired."""
    while True:
        reveal(*choices())
        if raw_input('Play again? (Y/N):  ').lower() != 'y':
            break
    print 'Have a nice day!'

play()


There isn't much benefit to having choices() produce both the player's choice and the computer's choice, though.  You should break that up into two functions.