Plugged heater core is a definite possibility, but a couple of other possibilities for starters. One is that the heater valve is not operating properly. This is a vacuum controlled valve, under the hood. You can see it easily if you trace the hoses. Check to make sure it's opening all the way. Also, do make sure your coolant level is sufficient. When it goes low it will often be enough to cool the engine, but the heater won't work.
Also, if you're a frequent reader of this forum you'll probably already know that vacuum problems can cause the heater to default to defrost, so when you seem to be suffering from the cold, make sure there isn't a bunch of heat coming out the defrost vents when you don't want it there.