Nearly half of young Vietnamese workers remain trapped in low-skilled employment despite education investments, contradicting human capital theory's prediction that skills enable upward mobility. We develop the "Skills-Mobility Paradox" theory explaining this puzzle through three mechanisms: institutional recognition gaps, mobility thresholds, and sectoral skill traps. Using Vietnam Labor Force Survey data (2010-2023) and sectoral case studies, we find threshold effects at 200 training hours, 40-60% recognition gaps for vocational credentials, and negative mobility returns to sector-specific experience (-2.3% annually). These patterns cannot be explained by existing human capital or segmentation theories. Our framework reveals that in segmented labor markets, the skills-mobility relationship is institutionally mediated rather than inherent. This challenges human capital theory's foundational assumptions and explains why education expansion fails to reduce inequality and why skills-focused interventions alone may be insufficient for promoting mobility in developing economies.