What are the different prefixes of Bitcoin addresses? Until today, I thought all addresses must start with 1.

Well, behold 3M8XGFBKwkf7miBzpkU3x2DoWwAVrD1mhk, which is a multi-sig escrow address created to hold the bounty for the development of CoinJoin. This is both the first address I observed that doesn't start with 1, and the first multi-sig address that I've seen in the wild.

Are there other possible prefixes? What characterizes the different prefixes? (E.g. are all addresses that start with a 3 multisig addresses? Are there multisig addresses that do not start with a 3?)
According to the glossary 
the possible prefixes for bitcoin addresses are 1,3 or 5:

I'm quoting here:


  Address
  
  Bitcoin address is a Base58Check representation of a Hash160 of a
  public key with a version byte 0x00 which maps to a prefix "1".
  Typically represented as text (ex. 1CBtcGivXmHQ8ZqdPgeMfcpQNJrqTrSAcG)
  or as a QR code.
  
  A variant of an address is P2SH address: a hash of a spending script
  with a version byte 0x05 which maps to a prefix "3" (ex.
  3NukJ6fYZJ5Kk8bPjycAnruZkE5Q7UW7i8).
  
  Another variant of an address is not a hash, but a raw private key
  representation (e.g.
  5KQntKuhYWSRXNqp2yhdXzjekYAR7US3MT1715Mbv5CyUKV6hVe). It is rarely
  used, only for importing/exporting private keys or printing them on
  paper wallets.