Do you remember if you had created a username and password when you previously completed this analysis? And, you are logged in as this same user now?
My guess is that you may have been acting as an anonymous user, in which case we won't be able to dig up the data from before.
Do you mean that there used to be a tool group named "NGS: Assembly"? I am fairly certain this was true for a short window on the public Test Galaxy site (http://test.galaxyproject.org/). I don't recall Velvet, just Trinity, but this server is under constant flux. Sometimes even tools on Main (http://usegalaxy.org) will be temporary or we simply re-prioritize content.
This makes me wonder if perhaps you were working at another public Galaxy instance? A list is here, and content can vary. Each is administered by those that own the site: http://wiki.galaxyproject.org/PublicGalaxyServers.
Going forward, if a public Galaxy isn't the right fit, using your own Cloud instance is a great option. Load the tool from the Tool Shed. Amazon has a grant program that can help cover compute/data storage costs (Galaxy is always free!). Here are links to get started:
Hopefully Dannon's and my answer helps out, it was a bit difficult to know exactly what you were missing.
Best, Jen, Galaxy team