I put a new furnace in (97% efficiency) because this home is so cold on the floors that my feet are cold anywhere I walk. Now have heat vents in ceiling but not helping any. Always cold, especially around baseboards (can feel the cold come in). Can't afford any major project. On SS and in debt for the furnace so hoping for a quick and cheap fix.
A quick and cheap fix is a warmer pair of socks.
As MDMoore313 says, the ceiling is not an ideal place for a heat register since the warm air will tend to stay at the ceiling. I can only speculate why your contractor installed them there: possibly as a cost-saving solution because access was easier or there was existing AC ductwork?
You may be able to mitigate the problem with a couple carefully placed fans to circulate the warm air off the ceiling. You want them on low speed and not directed at people, or else they will have a chilling effect. A ceiling fan blowing UP would be perfect for this situation, but even a small adjustable fan like a Vornado would probably help a lot.
You also mention that you can "feel the cold come in". Do you mean there's a draft? Getting your building envelope as airtight as possible should be your #1 priority. The most efficient furnace in the world is useless if all that hot air leaks out of your house. A tube of caulk or can of spray foam will pay for itself 100 times over if you can plug up any leaks.
If you have the budget for it, an energy audit may be worthwhile. The furnace is just once piece of the system. In particular, a door blower test or thermal imaging scan may help you identify areas that would benefit from extra sealing or insulation, which would both save you money and make the house more comfortable. Your state and/or utility company may offer free or subsidized energy audits.
It sounds like a draft is the larger problem here. Luckily a there are a lot of DIY projects you can do to help improve this, many of them cheaply. A draft detector (wax stick that puts off white smoke) will help you locate the worst offenders. Some common projects to consider: