I know that public domain is legal to use, but if I buy a CD of a performance of a public domain song that has been recorded recently is it still considered public domain?

Almost always: no. It's very simple to find out... just look to see if the CD is copyrighted.

I know that public domain is legal to use, but if I buy a CD of a performance of a public domain song that has been recorded recently is it still considered public domain?

No, this is not considered public domain.
If you have a local choir sing "Battle Hymn of the Republic," which is a pub-domain song, you could have them do a work-for-hire agreement, and the song is yours to use as you choose.
If you took the Mormon Tabernacle Choir's recording of the "Battle Hymn of the Republic" you could expect a lawsuit to be knocking on your door.

While the song might be PD, the recording is not. The recording carries its own copyright, held by the recording artist or his publisher. In addition, sync rights and mechanical rights become part of the story too.

The best rule of thumb is to assume that all recorded music is copyrighted. In practice it is very difficult to find out if any recording or piece of music is really in the public domain.

Looking at the CD won't do it because even if the performer is not claiming copyright over his/her performance that does not mean you have a right to use the music.

See: http://www.pdinfo.com/

And esp. http://www.pdinfo.com/record.htm

Any work of authorship that is fixed in a tangible medium is protected by copyright under U.S. law. Copyright protection arises when a public domain work is translated into a new medium, e.g. if a very old recording that has passed into the public domain is digitized and ANY "selection" is made, e.g. filtering, pop and hiss removal, etc., a new protectable work is created.

Any CD recording implicates multiple copyright concerns. Though the underlying work may have passed into the public domain, the recording itself may still be protected.

So are there any recordings of classical music available for legal use? Or do I have to have them performed and record it?

So are there any recordings of classical music available for legal use? Or do I have to have them performed and record it?
I'm sure there are some, if you have an old wax-cylinder player. There may be some phonograph records around which have fallen into the public domain. I'd be surprised if there were any CDs.

There are LOTS of libes of classical music created solely for the purpose of royalty-free/buyout (which isn't necessarily the same thing)
The cheapest ones can be found at Sam Goodies' or Camelot, in their Sound FX sections. Be SURE to look at the license, because sometimes they're not licensed for broadcast, but ARE licensed for mass production of non-broadcast product. I bought one last month in Walmart's bargain bin for 2.99, and it's got 9 classical selections that only needed EQ and some verb and they were quite usable. Sound Dogs has offerings, Weed has some, Freeplay has some, it's really all over the place.
Another option is to find classical midi files that someone has specifically said "you can use this" or "This is Public Domain" and use the MIDI files to generate your own orchestral sounds.
Finally, the local community orchestras usually are open for this for free or low fee. I've done this twice in SLC, Ut

Hi Douglas,
Many of my buyout non-needle drop libraries have various classical tracks that are useful from time to time. I'm curious about the disk you found at Walmart. Is this something you can use in a video production that will not hit the air?
Thanks - Jimmy.

Yes, the disk I found at Walmart specifically states :
"These sounds may be used for commercial sound design and audio composition, excluding audio or video presentation sent over public airwaves. You may not reproduce these sounds as individual sounds for purposes of resale; they must be incorporated exclusively into sound design or audio compostion. "Any unauthorized use yadayadayada."

I've seen other even less restrictive statements.

Thanks for the reply. Next excursion to the "electronic" department, I'll be sure to read the fine print.