The following are "Hard" problems, in the sense that no elegant (i.e. non-brute-force) methods exist...

1. Determine whether a given (odd) number is prime.

2. If a number N is composite, factor it (efficiently).

The difficulty of Problems 1 and 2 form the basis of the RSA encryption algorithm.

A nice article on public/private key encryption appeared in the Atlantic Monthly, September 2002.

The problem of coloring a graph with the minimum number of colors is known to be an NP-complete problem. [reference].

More discusssion on NP-Completeness, with many examples coming from computer science and graph theory.

The classic game of Minesweeper is an NP problem.