It also depends on the price you paid for that coach seat. On most of the sale/cheaper fares you can't use upgrades even if seats were available . In CO's view, Hawaii is not part of the "continental US", so they use the sames rules as on International fllights.
But all that being said, yes it's true it is very very difficult to get an upgrade on that particular route.