pretty url using custom post type and taxonomy with custom press

Hi there,

I have been trying to get the permalinks to look pretty but also be helpful.

I have diffrent custom post types that I would like to be organized by state. Similar to a directory but not quite so complex. I have a hotel section where I would like to list all the hotels in washington that that I have listed and on another link I would do all the hotel listings in Colorado. I have been able to get it to show all my Custom Post types showing the same Taxonomy but I am wanting for it to be more organized.

At the moment, this is what the links look like for me..
http://thetraveljoint.com/state/california/

This, of course, shows everything listed under the State of California. But, what I want is only all the Hotels listed in California.

Ideally, I would like the url to have the custom_post_type in there so it would be ..
http://thetraveljoint.com/custom_post_type/state/california/

That way things will be listed out properly and can list my content correctly.

If i do a search query, I can get the desired results but the URL look weird... http://thetraveljoint.com/hotels/?location=colorado

I have all my content split up into a custom_post_type then use a taxonomy to organize the content by location (state).

I tried using this plugin ...
http://wordpress.org/plugins/custom-post-type-permalinks/

It gave me the correct looking URL's but they all went to 404 pages.

Do you have any suggestions on how I can achieve what I am trying to do?

Thank you,
-mo