I found a different way to fix this. I still do not allow iTunes to manage my song library, so I have all my .mp3 files on a NAS drive in folders and didn't want to have to use iTunes to re-encode files and worry about getting them sync'd up with whats on my NAS drive.
I downloaded MP3 encoder from the Mac App Store and set it to bitrate 256, quality 10 (left method = CBR, stereo mode = auto, sample rate = auto)
I set preferences to Output the file "same as source" and had it Overwrite existing output files. What this does is sets the encoder to re-encode "in place" basically replacing the old file with the new one. This allows the songs to keep the correct pointers in iTunes (e.g. no re-copying them to iTunes)
I created a smart playlist that contains only the "waiting" files and right click each one, select "Show In Finder" then I drag the file in question into the encoder, encode, and magically iTunes somehow detects the song as needing to be re-sync'd to the cloud.
So basically by re-encoding them outside of iTunes but keeping the same exact name and location, its retriggering iTunes to re-match those songs.
Its a bit of a pain to have to walk through each one like that, but at least this way I'm not having to really touch iTunes... don't have to worry about removing songs, re-adding, making sure they get back to their proper playlists etc.
I processed about 50 files like this and all were either matched or uploaded. (once I got rolling it only took me a few minutes using this method)
I now have zero "waiting" files.