Terrain Toolkit related? I'll try that in a bit.
I think I figured this issue out. After some playing around, I noticed that by changing the Y value of terrain instead of setting the height and hitting 'Flatten' seems to cause this issue... or one similar. I initially noticed this when I had a flat piece of land on a hill I'd just made and the brush was actually showing up underneath the flat area, and the brush didn't show up at all anywhere that hadn't been painted on yet. It would, however, show up as I was painting and it would show up over things that had already been painted.
I set the Y position back down to 0 and used the same value in the set height brush and hit 'Flatten' and haven't had the problem. I'd say it's just something weird with positioning. This being the latest version of Unity (Reinstalled last night because I was wondering if I reinstalled, if it would fix the brush issue).
Anyway, if anyone else's having a similar issue (Or has such in the future) and you're using the Y position, set the height of the terrain instead.