There is no restriction about primary keys as Strings. I have a CMP Entity with such a primary key and the finder works fine.
You should post the exact message for the first FinderException in order to see the exact problem. When you change the primary key as Integer, did you change all is necessary (the table in the database, the bean definition and the descriptors (ejb-jar.xml and jbosscmp-jdbc.xml). Prehaps you are using XDoclet ?
If all is OK, perhaps the problem comes from the databse itself (MS-Access) or its driver. I use MS SQL Server for my application.