Direct3D Initialization Error D3DERR_NOTAVAILABLE

Reinstall drivers as sunnycoder said.
Also, reinstall DirectX and run dxdiag:
Go to Start, Run, type dxdiag and press enter. Run the proposed tests and check for errors coming up.

I reinstalled the graphics drivers, and even used a driver cleaner to remove all old files before reinstalling. However the problem still came up. I am thinking there be something wrong with a DirectX config, but not sure how to approach this, I've read people saying to just reinstall windows rather than reinstall DirectX. But if I were to reinstall DirectX, how would I do that safely?

I hope you are not using the Microsoft drivers but the ones which are supplied by your card vendor.

Run Directx

c:\WINDOWS\system32\dxdiag.exe
or c:\Program Files\directx

Check each tab and see if there are any errors below under notes.
See directx, display,sound,input and network

are there any errors?

D3DERR_NOTAVAILABLE is returned if the requested back buffer format is not supported, or if hardware acceleration is not available for the specified formats.

http://msdn.microsoft.com/library/default.asp?url=/library/en-us/directx9_c/directx/graphics/reference/d3d/interfaces/idirect3d9/CheckDeviceType.asp

This may be as simple as an ingame option.  Is there a Safe mode for this game?  Lots of games had a safe mode that will run in the minimal settings.  This will allow you to restore defaults if you have changed any of them.  If you have an older card, and tried to enable Shaders version 3.0 or somthing like this, it may cause it as well.

But, it soulds more like corrupt drivers.  Reinstalling the drivers and Driect X should have fixed this.

Any success frogpad?

I apologize for the delay, work is getting in the way of me fixing my video game issues (I hate it when that happens). I have tried everything, except I didn't uninstall directx, from what I have been reading, there is no safe way to do this. What I did was run the directx install program on top of my existing directx setup, but have the same errors.

I ran the dxdiag command, and I found an error under my display tab:
The file nv4_disp.dll is not digitally signed, which means that it has not been tested by Microsoft's Windows Hardware Quality Labs (WHQL).  You may be able to get a WHQL logo'd driver from the hardware manufacturer.

And under my sound tab:
The file cwawdm.sys is not digitally signed, which means that it has not been tested by Microsoft's Windows Hardware Quality Labs (WHQL).  You may be able to get a WHQL logo'd driver from the hardware manufacturer.

I tried doing a system restore, but for some reason it wouldn't let me and the error message was vague to the effect of "You can't do it" after running the restore for about 10 minutes. I am considering reinstalling my windows os sometime soon, because I have a slew of other issues that are affecting performance. But if there are any other suggestions out there, I greatly appreciate it. Thanks.

Those are not really errors, most driver work fine even without the WHQL significate. If you want to tackle a Windows reinstall It could help with sorting out that issue.