FANTASTIC NEWS. I have officially been able to get rid of the skipping issue altogether. For the record I have an HTC Evo.
Now some of you are going to hate me because like Snoksier, I also had done several things at once so I can't tell you guys for sure what fixed it. I will at least list the things I did from the least likeliest to the most likeliest to have fixed the issue.
First, I recently moved into a new apartment with a new connection, but I don't think this helped since it's still Qwest DSL and my connection speed is actually slower and I still have the same computer and modem. Plus I know this problem probably has nothing to do with any part of the network since only songs that have already downloaded skip.
Second and third thing I did was install the latest Subsonic Android AND server software with the new fixes. Of course I'm sure this is the first thing all of you who are still having problems did. In addition, I haven't changed any settings in either piece of software since I had skipping problems.
Fourth, and this is by far the most likely candidate, I flashed my rooted Evo with custom ROM "
Warm TwoPointTwo" which came with myriad performance tweeks and also removed Sprint and HTC's bloatware. I know that somewhere in the mix of that custom operating system lies the tweek that solved the skipping problem (whether it be process priority, ect..). Of course you could probably use a different custom ROM to fix the problem, but I can't speak on that.
BTW if you're worried about flashing your phone with a custom ROM, don't be. As long as you make a NANdroid backup (a COMPLETE backup) you can always simply revert to that state. I know people who routinely bounce between several ROMs on a whim and I'm thinking about doing so myself once I upgrade my SD to a larger capacity.