Any program in particular that you have in mind? For some reason this software is very hard to come by.
I agree on hard to find. My desktop at home has a it built in to the motherboard BIOS (EP43-DS3R). There used to be more of them around back in the ISA NIC days, the beloved 3C509 had a great little utility suite that booted from a floppy. It's going to be something specific to the NIC model as it is going to read non-standard registers in the Ethernet PHY device, so you are relying on the NIC manufacturer for this unfortunately.
Also if I do rewire it should I do shielded cables instead of UTP? I don't mind spending a little more to do it right.
I have always heard that having shielded wires (any and all kinds of wire) in a wall were always a way to go. It is a precaution to many things and reasons.
See my earlier post. You have to be very careful with the grounding of the shield otherwise you can get quite large currents and blow things up in the worst case, or have it act like an aerial and add more interference. It's generally not recommended.
One other thought, I wonder if you are simply running in to too long a cable. How long is the cable(should be less than 100m/328ft)? What is it rated at (Cat 3, Cat5, Cat5e)? What speed does your HTPC negotiate at (10Mb, 100Mb or 1000Mb)? Note that 1000Mb requires all 4 pairs to be working in Cat 5 or better whilst lower speeds use only one pair in each direction.