Hello,
I have done lots of SEO work with Joomla and Joomlart templates, the issue is NOT the template but Joomla and your server.
1st off Joomlart website templates do index very, very well in Google and Yahoo if you set things up right. We have many Joomlart sites that are front page ranked for their major keywords.
Some sites we will use .htaccess /mod-rewrite feature with a 3rd party extension like Artio to clean the URLS, but that takes some practice and good knowledge of SEO to set-up right. Plus many hosting companies DO NOT support mod-rewrite; please check that before you consider using this type of 3rd party SEO plug-in on your server.
If you decide to do this you MUST read all the documents 1st before you start to change anything on your server. Oh and make sure you BACK-Up, BACK-UP and BACK-UP! Before you start!
Have a look here for Artio I hope this helps.
Regards