I have a game that is rather dull and I felt like sprucing it up with random names (not generated ones however). Each name is in two parts, the first and last, both being chosen from a large list. Aside from celebrities would I legally able to take a phone book (or something similar) and just add names from it to the list of names?

Depending on the uniqueness of the name you might open yourself up to privacy/false light/misappropriation/invasion legal liability. These are civil suits that individuals can bring regardless of whether they're celebrities or not. They are privacy actions that don't protect the financial worth of the name itself, but the individual's privacy. If the name is distinct enough to make an individual person identifiable, and your game portrays them in a negative or false light, or otherwise exposes them, commercially exploits them or invades their privacy there may be grounds for a suit. There are also potential related claims for defamation. Tread carefully and randomize the names, keeping them as common as possible if you decide to go this route.