As to the original question:
Now, you'll have to listen to the song (see link) to put all this into context, but I'd change the line:
         
          "But that was long before we found the box"

to   " But that was up until we found the box"

What do we think?

I don't think either version really 'hits the spot'.
The singer's (previous) view of their father was formed before seeing the contents of the box of mementos. How 'long before' we don't know.
Finding the box (the alternate suggestion) doesn't change the view of the father, it is seeing the contents that evokes the change.

Possibly more suited (but more of a change to the lyric):
"That all changed when we looked inside the box."
or
"Our minds change when we looked into/inside the box"
or
"We knew him when we looked inside the box"

or, for the coda:
We all thought his heart was made of solid rock
But that changed when we looked inside the box
We all thought his heart was made of solid rock
We knew him when we looked inside the box.


Just thoughts.
The original author knew what he meant, and what he wanted to evoke.
Change for change's sake is not always a good idea. If the song has touched you enough to make you want to learn it & sing it, then surely it was the original words that so touched you. Possibly leave it as it is?

Cheers

Nigel