The Halifax/Maritimes issue is related to the absence of a suitable stadium. However, apparently the Atlantic file is being worked on several fronts, but is unclear at this point whether a team will end up in Halifax or Moncton.
In fact, Moncton will be a hosting a regular season CFL game this year:
Home | Touchdown Atlantic
Although Halifax is much bigger, some say Moncton has the inside track on a CFL club (more central location, new and expandable stadium).
As for Ottawa, it has been granted a conditional expansion franchise. Plus the city has approved extensive renovations to its stadium. Ottawa should be back in the CFL in 2012.
Ottawa's problem has always been bad ownership. It has rarely had good local ownership (some say because a government town has few rich local businesspeople), and in fact two of the most recent CFL owners in Ottawa were Americans.
The current group is locally-based and has deep pockets.
Also note that fan support in Ottawa was never really a problem, and with usually very bad teams attendance was above, at or near the CFL average, and often above the averages for many teams still in the CFL today.
Quebec City is also on the CFL's radar as well, but there are stadium issues to overcome there as there are in the Atlantic region.