Is there a database of known problems with information about their complexity and algorithms, related problems, references etc that is available to us? [If not, can we make one? I know this is off topic, but it would be SO useful]
If you do not insist on a database, the Encyclopedia of algorithms By Ming-Yang Kao is very valuable reference. The above link is the entry for the minimum Bandwidth problem.
This is an encyclopedia of algorithms that sets out the solutions to important algorithmic problems. It aims to be a comprehensive collection and is designed to provide quick and easy access for both students and researchers.” (Kybernetes, Vol. 38 (1/2), 2009)
There is a large list of algorithms and data structures on the National Institute of Standards and Technology governmental website: http://xw2k.nist.gov/dads/
It's not complete and I don't know how new algorithms, problems, and data structures can be added, but it has a decently large list. Links to implementations of each description are included, if available.
There are also links to additional resources near the bottom of the page.