So many strange things about what you said, but first, what is the exact routing? Nobody flies HNL-YYZ non-stop, not Air Canada (UA's partner) or UA itself. So, I assume it is something like CLE-YYZ-LAX-HNL or CLE-YYZ-YVR-HNL?

Anyways, to answer your question directly, you definitely need a passport to do an itinerary like that. You won't be allowed to board the plane in the first place, and once you arrive in Canada, your choices are going through Canadian immigration or through US immigration (for cross-border flight back into the US). Both require a passport.

As for the strange things, I know Air Canada cannot sell a US-Canada-US ticket legally. But maybe UA can, despite having to route through Canada. I'm not sure.

Also, how did you book your flight? I have never seen a US-Canada-US flight on united.com or the old continental.com. Whatever, you need to call whoever book you, or UA to have the ticket reissued with an itinerary that doesn't go through Canada.

I looked through Kayak and I had to request this routing, but to route this way is almost %500 less than a "normal " routing.(HNL-CLE-CLE-YYZ-HNL and then the reverse, as I don't know which direction the OP is going) SO maybe it was through a consolidator.

PS and it was all UA flights including an United Express, no air canada.

TO answer the q., you may be stuck as there's not an exception to the 24 hour rule for needing a passport. exp through a consolidator.

You might use your expired passport to get a new one through an expediter.

A $110 (or more) solution:
http://travel.state.gov/passport/forms/ds82/ds82_843.html

Thanks for reply. I searched HNL to CLE r/t through Kayak which transfered me to United website for purchase. I didn't add any extras to the search, just my departure city and arrival city. The return flight was CLE-YYZ-LAX-HNL...sorry I left that out. But not wanting to stress out trying to get passport renewed, I called the airline. First time I called they offered to waive change fee but not difference in ticket price, which would have been $350. I called back later that night and this time was transfered to international reservations. The agent looked at my itinerary, said "that won't work" and promptly changed it CLE-LAX-HNL at no extra cost. What an angel. Luckily all's well that end's well this time. Next time...I'll pay closer attention