Chinon seems to make a few very good bodies that rivals Pentax's own bodies in the 1970s, in both M42 and K-mount. Vivitar is basically an American company that imports stuff and rebadge them as their own brand name, so you'll find some Vivitar cameras that are actually made by someone else including Cosina. Cosina is also another popular K-mount replacement, as well as Ricoh but I think there's some lens compatibility with certain body-lens combo so you'll have to check it out if you're into Ricoh. And there are many other never-heard-before brands that takes K-mount and M42.
If you want to buy new bodies, Swedish-made Phenix DC828 (http://www.photax.se/kmrr/phenix/phenix.htm) is a viable alternative to a Pentax-brand camera for K-mount, while the Cosina Bessaflex (to be released, http://www.cosina.co.jp/bessaflex/) is a new M42-mount body with an old chassis. But frankly for the prices you have to fork out for these, you're better off getting a Pentax. As long as you keep away from the upcoming FA-J lenses, and the MZ-30/50/60/*ist (film, not the *ist D), any lense will fit on any camera.
K-mount compatibility is unsurpassed... with the exception of Pentax MZ-30/50/60/*ist film body, your K lenses will fit on any other Pentax bodies and will work just like how it works on your M-series bodies.
A good replacement M-series body may be hard to find... Fotographix at Lucky Chinatown has 2 MXes, one of which is near mint. They've also got a nice LX. The price is on the high side though I must admit they are beautiful. Sometimes Prime Camera and Camera Workshop carry used Pentax cameras. There's another shop on the 2nd level of Pennisular Plaza that displays some nice Pentax cameras. I forgot its name.
Alternatively, get a new MZ-5n or MZ-3. These are modern bodies with a clean, classic layout. All settings are done via dials and switches, not menus. The only difference between MZ-5n and MZ-3 is the different shutter mechanism - MZ-5n x-sync at 1/100 with top speed 1/2000, MZ-3 x-sync at 1/125 with top speed 1/4000.
With the digital SLR body due for release in August, you can mount the K lenses onto it and it'll work just like how it works on your M-series bodies... beautiful, isn't it?
Note the name for the DSLR though. It's the *ist D, not *ist. The Pentax *ist is another budget entry-level film SLR.
The *ist D is probably going to be affordable. It can't possibly cost more than the current offerings by the competition, and historically Pentax products are priced much lower than what the competition offers. My guess is that it might cost around $2k, probably not more than $2.3k.