Client in question found a public domain icon they really want to use as their logo (instead of having one designed, I know, I know). Is this legal?
If it is truly in the public domain (or has a public domain notice) you can use it for whatever you want. So yes, it's legal.
It may not be all that smart, though, given that anyone else can also use it as their logo. You may lose a good chunk of 'uniqueness' in that regard depending on the particular market you are in.
Using a public domain icon of a scale may be fine if you are a lawyer, as lawyers rarely compete based on branding.
But, on the other hand, if it's a product logo to be sold on a shelf, being able to differentiate oneself visually may be very important.
Also to add to DA01's comment if they are wanting to use it for a logo, you should address that the icon is public domain it will be hard to copyright their logo artwork if they try. Which would be a good selling point on creating a custom icon.
Furthermore, I would ask for documentation if they are asking you to develop something around the icon in regards to the actual rights so you will cover your own later on. You could be liable (not a lawyer though) and the person who own's the rights could and would try to go after you. So get the public domain information and attach it to your project for future reference.
If the client wants to use public domain artwork, suggest that they use a combination of 2 or 3 public domain artworks. When you put them together, they become something unique that you can defend a copyright on.
You can see examples of this in military crests that reuse anchors and other generic elements, but they always have 2 or 3 put together in some unique combination.
A key word to use is “unique.” The most important thing with a logo is that it be unique.