It should be a gray circle and slash on a gray background. A little like a no entry sign. Because you mention a red circle on blue background this might indicate a GPU or Display hardware problem?
When you replaced the hard drive did you insert one with a pre-installed operating system? If yes what version? If not how did you install the operating system and what version?
There are a number of possible reasons why you might see the no entry sign.
The operating system installation went bad for some reason and/or the drive you installed it on developed a problem almost immediately after the install. You're trying to boot older hardware using a newer operating system. The only way this could happen is if you installed the operating system on a disk connected to a later model mac and subsequently transferred the drive to the Powerbook.
There's also a remote possibility you're trying boot newer hardware using an older operating system.
The maximum OS you can install on that hardware is 10.5 (Leopard). If you don't have the installer disk you will need to find and purchase a universal DVD installer unless you can locate the gray coloured machine specific DVD Installer for it? eBay possibly? You don't mention how much RAM you have? For Leopard you will need 1GB as a minimum. The maximum RAM that hardware supports is 2GB.
Supported RAM Modules are the PC2700 DDR333 200-pin SO-DIMM type.