I used a class set (I am a teacher) of standard hard bristle paint brushes in a Elmer's white glue and water mixture. Despite washing them numerous times with water and hand soap, they are still rock solid when dry.
Soaking them in warm/hot water is the common procedure for removing Elmer's glue. Elmer's glue is specifically water-soluble — so if it isn't coming out then maybe it is not Elmer's.
Make sure the water is warm/hot throughout the soaking.
You may need to peel-off the outer layers of glue, first, and then re-soak to loosen the next layer.
Although this link is for the removal of Elmer's Glue from clothing and fabrics, the basic principles can be applied to paint brushes too.
How to remove glue from clothing and fabric:
When dry, do not use hot water, dry cleaning solvents, a hot drum dryer or iron before the removal of the adhesive is complete, as they can fuse the adhesive film irreversibly, making removal impossible. Soaking in room temperature water for 24 hours or longer will help to redisperse or soften the film. After soaking, wash the fabric in a normal wash cycle and allow it to dry at room temperature. Check for discoloration and stiffness on drying. If so, repeat the process until the item is cleaned to your satisfaction. Watch the video "How to Remove Elmer's Glue and Glue-All from Clothing" to learn more.
I have a jar filled with water to put my brushes in when using Elmer's Glue in order to avoid this very problem.