There can be a number of issues.
Some newer AGP cards do indeed require a newer AGP slot that supports 8X AGP.
The difference is that the older slots do not support the 3.3 volt power that newer cards require.
You may not have enough RAM for the new card.
Generally, you need to have twice the amount of video RAM installed as system RAM.
For a 64MB video card, you need to have at least 128MB of system RAM.
A common problem that I have run across is that the case design does not allow the AGP card to fully seat in the AGP socket.
AGP cards use an interleaved connector.
If the card is just a few 0.001" from being seated, the card will not function.
When I suspect that an AGP card is not fully seated, I remove the metal bracket from the card and see if it seats further into the socket.
If it does, I modify the metal bracket as needed.
Usually, all I need to do is file the video connector mounting holes a little.
Chas