For a hundred and fifty years Archaeopteryx lithographica has been the earliest known bird. The first specimen (actually a single feather) was found in 1861, in the Solnhofen limestone quarry in Bavaria, a fossil Lagerstatten (remarkable fossil bed) noted for exceptionally well preserved specimens; a number of other specimens followed. Archaeopteryx dates from the Late Jurassic, 150 million years ago. It shows clear dinosaurian affinities, but also has many birdlike features, most notably well developed flight feathers. It has been noted that had feathers not been found on Archaeopteryx, then it would probably been classified as a small dinosaur rather than a bird.
Archaeopteryx lithographica.
In the 27 July 2011 edition of the journal Nature a team lead by Xing Xu of the College of Life Science, Linyi Normal University announced the discovery of an earlier bird fossil. Xiaotingia zhengi, discovered in the Tiaojishan Formation in Liaoning, China is 155 million years old, or for convenience 'Early Late Jurassic'; fully five million years older than Archaeopteryx. Like Archaeopteryx, Xiaotingia shows both dinosaurian and avian features, though this is less remarkable than it was 150 years ago; many 'bird' features, such as feathers and wish-bones, are now known from a variety of dinosaurs. Nevertheless palaeobiological analysis of the fossil suggests that Xiaotingia is more closely related to modern birds than Archaeopteryx, and therefore can confidently be described as a bird.
Xiaotingia zhengi.
This is where things get a bit complicated. According to Xu et al. then if Xiaotingia is more closely related to modern birds than Archaeopteryx, than possibly Archaeopteryx should not be described as a bird. This is to do with the way birds are defined. If we define birds as modern birds plus all modern birds, plus their most recent common ancestor, then Archaopteryx is clearly not a bird as nobody thinks it is a direct ancestor of modern birds. Unfortunately all modern birds may well have had a quite recent common ancestor, which would mean that some Cretaceous fossils which are clearly very avian, such as Hesperornis might not be birds either.
So palaeontologists use a compromise definition, anything more closely related to modern birds than it is to Deinonychus (a dinosaur thought to be closely related to birds, but definitely not a bird) is a bird. This was fine up until now, as Archaopteryx seemed to be more like a modern bird than it seemed like Deinonychus. However Xiaotingia has more bird-like features than Archaeopteryx; producing a cladogram (family tree) for birds and bird-like dinosaurs including Xiaotingia moves Archaeopteryx closer to Deinonychus, and therefore away from the birds.
Deinonychus antirrhopus. Not a bird.
Ultimately though, this is about how we define birds as a group. Archaeopteryx clearly cannot be described as the earliest bird any more, but it should not be excluded from the group because of an artificial classification which was basically set up to rule it in and feathered maniraptiforms out. Only if good biological evidence that it is not sensible to describe Archaeopteryx as a bird comes to light should it be excluded. Sometimes technical definitions need to be tweaked to fit popular conceptions; if they did not then the definition of birds as we have it would not exist, so there is no reason to try to alter popular conceptions to fit the definition if it becomes obsolete.
See also The Ashdown Maniraptoran, An Australian Spinosaurid and Dinosaurs on Sciency Thoughts YouTube.