At first it seemed possible that the reason was just that they were both formerly Portuguese holdings. However Aden wasn't annexed until two centuries after the British took control of Bombay.
Is there a stated justification for why Aden fell under the jurisdiction of Bombay and wasn't placed elsewhere in the colonial structure? Was it as simple as there being no better place to put it?
Then as a follow up, what sort of administrative difficulties, if any, came up as a result of the distance and truly staggering differences between the cultures of the two places? For example, are there recorded incidents where the governing bodies of Aden were in direct conflict with those in Bombay?
It's been a bit difficult to find anything as far as justification from the past hour of reading up on this topic, so I could really use some clarification from someone in the know.
The short answer is that Aden was an ideal natural sea port thanks to its volcanic formations.
Its location, which gained more importance with the opening of the Suez canal in 1869, made it a necessary stopover for ships heading for India and the east all the way until 1967 when the UK left PDRY. The Lonely Planet Yemen guide claims that in the 1960s Aden's duty free market was the third biggest in the world after London and Liverpool
From French poet Arthur Rimbaud's letters to his family (when he stayed in Aden for few years), it appears that the city itself had no value other than the refueling of ships with coal and as a base for protection of naval trade. Therefore it seems that it is natural for it to be included under Bombay.
Aden's status as a trade hub (essentially what Dubai is now) explains why the British left little traces of their presence there for 129 years (as opposed to say Karachi or Delhi) apart from the tanker port, the water reservoirs, the oil refinery and the Sira brewery.
Let's go into a bit of background about British history in India before I try to directly address your question.
From 1757 until 1857, British rule in India was let out to the British East India Company. In 1757, a large majority of Company territory was in Bengal, but there were also the isolated coastal outposts at Madras and at Bombay, as shown in this map of holdings in 1765^1. So, the EIC chose to divide administration into three presidencies, the Bengal, Madras and Bombay presidency, each with their own governor.
These presidencies also had their own armies, regiments raised by the East India Company. In 1820 the Bombay Army consisted of 2 European infantry regiments and 26 regiments of native Indians, as well as three cavalry regiments and a company of miners and sappers.^2 At the same time, there were also regiments of the British Army stationed in India, next to company regiments.
To finally answer your question, the annexation of Aden happened in 1839, and it was under the initiative of Sir Robert Grant, the EIC's Governor of Bombay. Grant seized upon the plundering in Aden of the British flagged ship the Darya Dawlat as a diplomatic grievance against Muhsin ibn al-Fadl al-`Abdali, Sultan of Lahej. After half-hearted negotiations over compensation for the lost cargo, Bombay Army regiments were called in to press demands for the city of Aden as compensation.^3
So, in 1840, if you were to ask the Secretary for the Colonies in London why Aden was administered by Bombay, he would answer that Aden was not under his authority as a Crown colony, but was under the Authority of the East India Company.
The map declares the territory to be "British", not making a distinction between EIC territory and Crown colonies.
"Bombay Army" entry from The Victorians at War, 1815-1914 by Harold E. Raugh, jr.
The History of Aden, 1839-72 by Z.H. Kour, pp. 8-11
