I run vista (sadly...Lord knows I hate it) and redshark works fine for me. I got the latest version (4.00)....not sure what you have or if it makes a difference.
I got it to work. Jaysee from the Pokebeach chat helped me. When it asks you where to save the file when downloading redshark, save it to your desktop. It should work now.