Deprecated is 'formally' used when a class/method has actually be replaced by a new preferred way of doing things. Keeping the deprecated method is often used for maintaining backwards compatibility.
Legacy classes are classes that should no longer be used and are 'obsolete' but are still around because they are usually used internally by Java itself (e.g. They are classes that you don't directly interact with, but Java itself does).
My explanation perhaps isn't the clearest, so hopefully some others will pop in and answer as well.