Common causes for this problem are an incontinent water inlet valve or low water supply pressure (such as from being hooked up to an RO filter) which doesn't have enough pressure to seal the valve. Another common cause, and the easiest to fix, is to replace the plastic water fill tube in the back of the icemaker with the new aluminum one:
Update time - I purchased the IM fix kit ( http://www.repairclinic.com/PartDetail/Hose-Tube-or-Fitting/584739?modelNumber=KSSS36DAW05%20%20%20%20%20%20%20%20%20%20%20%20%20 ) which replaces the PVC fill tube with an aluminum extension. It turns out this model (or at least our refrigerator) has a heater that goes around the tube. Apparently the PVC is non-conductive enough that the heater doesn't really work well. Also, I noticed the PVC would hold a drop of water in the tube with each fill (like how a bead of water sits on your hood after a wax job) - the aluminum tube allows the water to completely drain, and the heater can do its job.
Anyway - it works now. No more freezing up. Its been a week and no issues.
On a side note - the water dispenser nozzle decided to get brittle and shatter. I read all about how the tubing has to be fished through the door hinge and spliced under the fridge. Well, it turns out on this model the coupling is behind the dispenser insert. A couple of screws, dispenser pulls out, and a compression fitting is revealed. Took about ten minutes to get the new one in. Now we're ready for the next appliance that wants a little attention.