Could it have been Jacaranda? There is a big misnomer with Jacaranda being used to describe rosewoods as well as the flowering tree that also yields a useful lumber. It seems there are a lot of different woods that people label as jacaranda.

What you describe sounds like Paulownia. Paulownia is very lightweight, rot resistant, and flexible. It is a great wood for kayaks, surfboards, and anything where weight is a consideration. It is commonly used in Japan and China in furniture making.