Logged In: NO

I had the same problem.
Everything was working fine, until I tried to add some more videos to the songs. So I had to convert them to make em smaller (you don't want a 40mb video for every tune when you have more than 200 songs). After I started UltraStar again - I realized that it's "singing itself". A quick look in the Windows sound settings brought the clue..

Try the following within Windows:
Control Panel -> Sounds and Audio Devices -> Device volume [Advanced...]

The Volume Control will open (yes you can also double click on the "speaker icon" left to the clock in the taskbar)
Options -> Properties -> Adjust volume for [Recording] (check that) -> [OK]

We're almost there ;)
Check if you Microphone is selected as your input device, also make sure that everything else is set on "mute"

* This might not be perfect solution, but it did help over here cause the programs I used to convert the video files created some sort of loopback - so my microphone was on the same "channel" as the "audio out".

Maybe it's helping some of you, thanks Corvus5 - you're awesome :)

If nothing works - always try to turn it on and off again :P