If I get some code off of the public domain, and I make major changes, can I re-license it and put my copyright on it?
Yes. If something is truly public domain, then there is no copyright it at all. Note that only your changes are under the new copyright, not the original public domain code.
However, it sounds like you might have found code that is posted with no license. If this occurs, technically the default copyright is "all rights reserved". In that case you should ask the author to specify a license. I actually had to do this earlier today.
An additional caveat: since any source code you find is probably less than 70 years old, you should still ask the author to use a public domain equivalent license, because there are some weird legal issues in Europe.