Terremark, the cloud and data center services arm of Verizon, has announced that Kerry Bailey will be leaving the post of president to take over the chief marketing officer position at Verizon Enterprise Solutions. Replacing Bailey will be Nelson Fonseca, most recently Terremark’s chief operating officer, as the company moves to accelerate its cloud business.

Before reaching that COO post, Fonseca was president of Terremark’s U.S. Public Sector business, overseeing the company’s relationships with federal, state and local government bodies. Perhaps more importantly, his duties also called for his oversight on Terremark’s Virginia-based Capital Region NAP, the lynchpin of its services for its powerful and influential customers in the greater Washington, D.C., area.

Bob Toohey, Verizon Enterprise’s COO, explained the timing of Fonseca’s appointment to the new role in a prepared statement:

A lot of that groundwork already has been laid: In addition to the aforementioned Capital Region NAP, Terremark recently expanded its European presence with a new flagship Amsterdam data center. Even earlier in 2011, Verizon acquired cloud migration tool developer CloudSwitch as part of a larger play to enhance Terremark’s portfolio.

We’ll be keeping a close eye on Fonseca’s reign as Verizon tries to conquer the cloud services market, so stay tuned.