Are you just using HDMI over CAT baluns or are you using a HD-Base-T unit?
I strongly recommend that you give the Monoprice HDMI HD-Base-T units a try.
Single (not double) Cat-x cabling. I have personally tested it at 300 feet with a 1080p signal using 3 pieces of cat-5 cabling and in-line couplers. Ran the test pattern for four hours without it dropping out once.
I have not moved them into about half a dozen installations with excellent results, including my own home setup where they perform perfectly.
HD-Base-T and true derivitives of it are phenomenal.
I used several HDMI balun solutions with double cat cabling, and they all sucked. The Monoprice one worked reasonably well up to 1080i resolution, but could not handle (despite claims it could) 1080p.
It is strongly recommended that you use Cat-6a STP if possible. Monoprice has pre-terminated 6a STP cables available on their website.
This:
For only $180.90 each when QTY 50+ purchased - HDMI® Extender Using Cat5e or CAT6 Cable - Extend Upto 328ft
and this:
Cat6A STP (Shielded Twist Pair) Straight Cables - Monoprice.com
I spent several years going through half a dozen different solutions before I started using HD-Base-T and I will NEVER go back.
Yes, never use EZ-RJ-45 connectors for anything. It is better to terminate your cables to a punch down block and then use a pre-fabricated cable as well. Patch cables have a rated life of just a couple hundred insertions before they are spec'ed to wear out.