I'll talk about the paper cutters (aka robocutters) first, since this is going to be image heavy. You're not looking for a Cricut, since they don't allow you to use your own patterns: what you want is a Craft Robo. The CC330L-20 is just fine. It hooks up to your PC (not Mac, alas) so that you can download the patterns that tell it where to cut. Alternatively, there's the Silhouette — also perfectly reasonable. (Note that five years later, as of 2015, Craft Robo and Silhouette have merged and the Craft Robo discontinued in favour of the “Cameo” model of Silhouette. Both are available from Graphtech, while older Craft Robos can still be found second hand.)
$150 is kind of an exaggeration, unfortunately. You can find them used on EBay for that price, but you have to be pretty patient. We're talking more like $200–300 for a new one. I should also note that a robocutter isn't a necessity — I do a lot of papercraft, and I don't use one. Some of the newer World Works Games models in particular are complex enough so that it'll make a big difference, but I just avoid those.
You might want to check out the Fat Dragon intro guide (PDF, 20 megs). It'll give you a good idea of what the hobby entails without a robocutter.
The vendor you were talking to was one of two possibilities. The first is Fat Dragon Games; their big castle set is Borderland Keep, although they're working on a new castle series. Here's a picture of Borderland Keep:
The other possibility is World Works Games. If you were looking at their stuff, you were probably looking at CastleWorks:
Both companies do really good work. Fat Dragon models tend to use up less ink, since World Works models use very saturated textures. Many people who do a lot of papercraft mix and match. Also, both companies provide the special files you need for the robocutters. You were probably talking to World Works Games, since they tend towards more complex designs.
The third really notable company in the papercraft field is Dave Graffam Models. His models tend more towards houses and single structures; he doesn't have a castle set, although his Medieval Walls set might be interesting to you. He does not supply robocutter files.
There are a fair number of other companies that have a few models; RPGNow stocks most of them.