Airport staff will now carry out extra screening of people from 14 countries, including those the US considers to be state-sponsors of terrorism - Cuba, Iran, Sudan and Syria.
Yemen and Nigeria - through which the alleged bomber travelled - also face the new restrictions.
Passengers flying from other countries will be checked at random.
On Monday in Paris, French foreign ministry spokesman Bernard Valero told reporters their Yemen ambassador had decided the previous day to suspend public access to the embassy.
Clinton says Yemen is a 'top concern'
French citizens in the country had been warned to be vigilant and limit their movements, he added.
The US was the first to announce the closure of its embassy on Sunday, citing "ongoing threats" by al-Qaeda in the Arabian Peninsula (AQAP), and the UK followed suit.
A US diplomat told the Reuters news agency on Monday: "The embassy is still closed again today... We are continuing to make the security review."
The Japanese foreign ministry said consular services had been suspended at its embassy in Yemen but other business was continuing, AFP news agency reported.
The German foreign ministry confirmed security had been tightened at its mission but that the embassy remained open.
BBC correspondent in Yemen
There are numerous security challenges in Yemen. The government is corrupt and unpopular, so backing it to fight al-Qaeda is risky, while the use of US missiles and drones to kill al-Qaeda leaders is very sensitive.
An overt US military presence is politically impossible, as Yemen is a conservative tribal society where hostility to the US runs deep.
Yemen is being torn apart by a tribal rebellion and a secessionist movement. This has been a bigger priority for the government than al-Qaeda.
Government authority in much of the country is non-existent. Tribal chiefs run these areas, and are sometimes willing to accommodate al-Qaeda militants.
Other issues include worsening poverty and unemployment, already the worst in the Arab world, and the jockeying for power among different factions as President Ali Abdallah Saleh ages.
Spain restricted public access to its embassy.
The Yemeni authorities have tightened security measures at Sanaa's airport, as well as around several other embassies.
Yemeni security forces, meanwhile, shot dead two militants north of the capital, Sanaa, said officials.
The US embassy was the target of an attack in September 2008 in which 19 people died, including a young American woman. The attack was blamed on AQAP.
On Sunday, the US deputy national security adviser for homeland security and counter-terrorism said there were "indications that al-Qaeda is planning to carry out an attack against a target inside of Sanaa, possibly our embassy".
John Brennan told ABC the group had "several hundred members" in Yemen and Saudi Arabia, and was posing an increasing threat.
Last week, AQAP urged Muslims to help in "killing every crusader who works at their embassies or other places".
The group also said it was behind an alleged failed attempt to destroy an Amsterdam-Detroit flight with nearly 300 people aboard on Christmas Day.
Mr Brennan told CNN there were "indications" a radical US cleric of Yemeni origin had links both to the Nigerian charged with the bomb plot, and the man accused of November's shootings at a Texas military base.
Mr Brennan said Anwar al-Awlaki seemed to be linked to the bomb plot
He said the preacher, Anwar al-Awlaki, had had contact with Umar Farouk Abdulmutallab, while he was allegedly being trained by AQAP operatives last year.
It was clear, he said, that Mr Awlaki had also been in touch with Nidal Malik Hasan, the US Army major charged with shooting dead 13 people at Fort Hood.
On Saturday, the head of US Central Command, Gen David Petraeus, visited Yemen's President Ali Abdallah Saleh to pledge support for its fight with al-Qaeda, after Washington doubled its counter-terrorism aid.
Yemeni officials last week said they had sent more troops to hunt down al-Qaeda militants in the provinces of Abyan, Baida and Shabwa.
Correspondents say the security situation in Yemen is complicated by an abundance of firearms, an insurgency in the north and a secessionist movement in the south.
But the prospects of re-asserting central government authority over the lawless areas where al-Qaeda is based look, in the opinion of some analysts, remote - even with beefed-up American support.
This page is best viewed in an up-to-date web browser with style sheets (CSS) enabled. While you will be able to view the content of this page in your current browser, you will not be able to get the full visual experience. Please consider upgrading your browser software or enabling style sheets (CSS) if you are able to do so.