The Goldbach conjecture is reasonably well known:
every integer can be expressed as the sum of two primes.
Very easy to state, but it seems very difficult to prove.
Terence Tao, a Fields medalist, has published a paper that proves that every odd number greater than 1 is the sum of at most five primes. This may not sound like much of an advance, but notice that there is no stipulation for the integer to be greater than some bound. This is a complete proof of a slightly lesser conjecture, and might point the way to getting the number of primes needed down from at most five to at most 2.
Notice that no computers where involved in the proof — this is classical mathematical proof involving logical deductions rather than exhaustive search.