change permalink structure for custom post type

Hi, I use a theme that had registered a custom post type and a custom taxonomy the rewrite rule in the register_post_type is:
'rewrite' = array ('slug'=>'ads','with_front'=>false),
changing the permalink structure in settings->permalink makes a difference only for blog posts not for custom posts.
The thing I’m trying to achieve is to get from this:
http://www.mysite.com/?ad_listing=9th-misc-ad
to
http://www.mysite.com/imobiliare/?ad_listing=9th-misc-ad
or better:
http://www.mysite.com/imobiliare-%city%/?ad_listing=9th-misc-ad
From what I’ve read I guess this could be made from .htaccess but I’m not very familiar with that. Hope somebody will help. I’ll really appreciate it!
Regards