@etan,
It sounds pretty normal.
Dogs have a natural instinct not to dirty their own living area, and a crate is the only thing small enough for a puppy to recognize as "his living area". The crate also teaches the puppy that he can hold it for a while. Obviously there's a limit to how long any puppy can hold it, so you have to give them frequent breaks outside especially when they are very young.
It takes between 4 to 6 months for most puppies to begin to recognize the whole house as "their living area" enough to trigger the instinct not to dirty it. When they are very young the house is enormous to them so they don't differentiate it from "outside".
During the first few months, a puppy will have accidents at any time/place in the house, so it's a good idea to keep them in the crate any time you're not watching them.
If they have an accident in the house it's ok to discourage them by pointing it out and saying "no", but be gentle about it. The house-breaking process has more to do with repetition than it does with vehemence. Eventually the dog will "get it". And it usually happens suddenly. My dog became house-broken after she got old enough to understand guilt. Then it only took one accident which I acted suitably appalled at and she suddenly got it. She hasn't had any accidents (other than illness related) after that.
In the mean time, keep plenty of paper towels and cleaner on hand