Ok Donny, follow me, I just did this on Vista:
Open MS Paint
Click Image > Attributes
I think the width and height for icons in Vista go up to 256 by 256, for
this example, we will choose 128 x 128
Click OK
Edit the image the way you like
Click File > Save As
Save it to a location where you can easily find it, I chose the desktop
I saved mine as test, choose 24 bitmap as the file type.
Close paint, go to desktop
select the "test" image file, rename test.icon
Select the application's executable you would like to change
Right click it
Click Properties
On the Shortcut tab, click "Change icon"
Click "Browse"
Select desktop
Click in the file type list box, click "All Files"
Select test.ico
Click Open
Click OK
Click OK
If a permission dialog pops up, click "Continue"
and there you have it.
I hope this satisfies Richard Urbans curiosity to find out if I know what
I'm doing.

Tried and tested on Windows Vista Ultimate x64 and it works 100%
If you are working in an image editor such as Photoshop, save your images as
.png to maintain translucency.