I bought my roadbike a few months back and the bearings in the stock shimano 600 headset were toast. The fork also shuddered and make a clicking sort of noise under braking. I just replaced the headset with a new Dura Ace (1" threaded). Its buttery smooth but the fork shudder is still there.

I haven't toed in my brake pads which I know could cause this. They don't seem to be able to be adjusted left to right, only up and down in the caliper. When I hold the front brake and rock the bike forward and backwards, I can literally see the fork blades bend back and forth. I'm wondering if this fork is shot? Its a kinesis aluminum.

Place your finger under the bottom cup/cone of the headset and repeat your experiment holding the front brake and rocking the bike. Do you detect motion in the headset with your finger? If so, the headset is too loose.

Yeah, check if the headset is loose first. But I wouldn't ignore flex in the fork. Some flex is normal, but hard to describe how much. If it is a bonded aluminum fork, there is the rare possibility that one of the joints is coming loose which is extremely dangerous. I'd have someone knowledgable take a look.

Shudder under braking can be caused by a lot of things. Towing in the brake shoes is normally done to remove squeel, not shudder. First checks are to clean/sand the brake shoes, clean the rim. The clicking could be the seam where the rim is joined going through the brakes (this will normally be opposite the valve stem.) Check for loose parts/play on the brake caliper as well.