Hi Michelle,
Looking at your site structure, it doesn't look complicated to change your site URLs. Of course there are the risks but I don't think its difficult.
From what I see, you have a proper structure followed, even though its non SEO optimized. For instance you have categories like - http://www.formica.com/en/home/ProductLine.aspx?start=1&prl=PRL_SOLID_SURFACING and http://www.formica.com/en/home/ProductLine_Colors.aspx?prl=PRL_LAMINATE&cls=CLS_180FX# and individual product listing pages like these - http://www.formica.com/en/home/dna.aspx?color=3461&std=1&prl=PRL_LAMINATE&mc=0&sp=0&ots=&fns=&grs=
You can try fixing these from within the webmasters tool using the dynamic parameters tool for a start.
You need to go for a complete URL restructuring only if it doesn't work.
Also, I would suggest using a good sitemap indexer to create a sitemap of all the individual listings and categorical pages with the right priority settings first. Google bots are clever these days because once the URLs (dynamic) are indexed via a sitemap, even if you have dynamic URLs they will figure the rest out from the content.
So, I don't think URLs are going to help you in a very significant way so it might not be worth the risk assuming that you have to do some major CMS changes to make it happen (and hope you don't screw anything on the way).
Get the basics right first like sitemaps, unique meta information and content. Then submit a sitemap and iron out the wrinkles using the dynamic parameter tool.