Do you have them hidden, or have you shrunk them down off of the screen? Try holding your pointer over where they would normally be, if you see a little arrow pointing up and down, click your mouse and move it up a bit. If the taskbar pops up when you put your mouse over where it should be, you're just hiding it. This can be changed by right clicking on it after you highlight it, clicking properties, then just uncheck the "Auto-hide the taskbar" option.
Sounds like windows driver issues. I am assuming it worked prior to the new video card.
1. Put the old vid card back in.
2. Download the newest drivers for your new video card.
3. Switch to the windows default video driver. (max rez should be 1024 if you are using winxp)
4. Shutdown and put the new vid card in.
5. Boot up and update the video card drivers using the downloaded file and not the file on the disk the Vid card came with.