I'd start with a 3D app and composite and add other elements in AE. Duplicating that exact video in AE alone would be a real pain. In AE with Element 3D or Waxworks it would be doable, starting in C4D (not lite but paid) or in Blender (open source and free) would be the way to go.
Well, I know if I want a 3d model spinning around like in the video I would use Element 3D. And I Also know how to make the cool graphic user interface things in After Effects, But what I'm trying to wrap my head around is how to make a galaxy/space type environment for the camera to fly all over the place without it looking like its just flying past 2d images of space.
You could make nebulas with Particular/CC Particle World.
Also, Particular has a handy preset you can start from to make a starry sky background behind everything.