It would depend on the agreement you signed with the attorney (and drafted by the attorney, of course!). Personally, I don't think the attorney should be liable if it's found your company hasn't invented anything.
A perfect patent search is impossible. There're over 9 million granted U.S. patents, so you need to narrow your search scope, typically by 1) patent classification, 2) keywords, and/or 3) inventor/assignee. Depending on your resource, you could either review thousands of patents or narrow the search down to a few hundreds. Then, from the search result, you determine which patents are relevant.
Even with large resource, you could still miss a relevant patent because it's not classified as you would expect it to be (e.g. a submarine patent), or it describes the invention in a atypical manner. Different people describe the same thing differently. Sometimes, a patent applicant could deliberately invent new terms to prevent the examiner find the relevant prior arts.
Depending on your resource, you'd also need to search patents in other countries.
Also, a US patent application is protected for a year before published. This means by the time your search report is done, it's already outdated.
Also importantly, competence does not occur overnight. You are the manufacturer and undoubtedly have studied many existing umbrellas in detail, and you have a better understanding of the manufacturing process & market needs than your attorney. Thus, you and your attorney may have a very different view on what's relevant and what's not.
It takes time for your attorney to learn your industry and gradually refine patent search strategies based on past mistakes. Thus, you need to carefully consider if you want to continue working with your attorney or if you want to have a new start with another.
Right now, your first priority should be asking 1) does your product infringe on the patent you just found? and 2) do you need to change your patent claims to get them granted?