The fact that the drive is at least partially recognized in BIOS is encouraging. If the Ultimate Boot CD thinks the problem is corrupted info, chances of recovery are looking a little better. I'd recommend two steps. Both of these can find and fix some things, and most of the work will NOT change the drive's contents unless you are sure they will do everything you want and allow it to do something.
First step, I suggest, is to run a series of diagnostic tests on the drive to look for hardware problems. From what you describe there may NOT be any hardware trouble, but it's good to check for that first. You don't say which manufacturer is involved, but many make available on their websites for free download a package of diagnostics. Seagate's is Seatools for DOS, WD has Data Lifegard. In each case I recommend downloading the version that has you burn your own CD-R disk with all the utilities. Then you boot from that optical disk and it installs temporarily a mini-DOS in RAM and then runs the menu-driven diagnostic package, all completely independent of any Windows OS on your machine. You run all the tests and see what it says about problems and whether they can be fixed. IF it says it can fix a problem for you, check very carefully what it proposes. If it is just moving data around to alternative places that's OK, but you don't want to do anything that writes a bunch of stuff and destroys data. When done you simply exit the software and see whether that has made any difference in access to the disk's contents.
The story you tell sounds a bit more like corrupted key components in the disk's hidden structures that track the files. That kind of problem MAY be solved by File Recovery software. There is freeware to do this, and third party software you pay for. In the latter category, one package many have had success with is GetDataBack - their website has versions for disks formatted originally with either FAT32 and NTFS File Systems. They have an interesting way of operating. You can run their recovery software on your disk while on the website for free. After whatever time it will show you exactly what it believes it can recover - even to letting you "open" and examine individual files and folders. If you think it will do all you want, you can pay their price and it will complete the job (I believe you actually have to copy the recovered files to another drive) and leave you with a licensed copy of the software on your machine. On the other hand, if you don't think it will do the right stuff, don't pay and nothing on the drive is changed, so you can try other tools later. This just might find the troubled corrupted data and either fix it or work around it well enough to recover most of the disk's info.
Anytime, as you are working, that you encounter an error message that says the disk is unusable and needs to be formatted, DO NOT DO IT! Avoid writing anything to this disk until you have recovered as much as possible. AFTER that is recovered you can decide, based on all the info gathered, whether to clear off the disk and re-use it, or throw it out and replace it.