I had a similar issue on a website i created.
It depends on how the custom post type is created and if there are other plugins that interfere with the permalink creation.
In the permalink section, what did you define ?
On the problematic website I had something like this :
personalized structure : http://mysite.com/%postname%/
Which i needed to change to http://mysite.com/article/%postname%/
Then the custom post types were accessible like this :
or like this : http://mysite.com/?myposttype=particularpost
This was caused by the no category base plugin which added some strange rewrite rules to the .htaccess file at the web site root.
However, i confirm that on other websites I am working on, custom post types work just fine with normal permalinks.