There are about 100 things this could be so I'll start with some basic questions:  
- Does the page your requesting to view exist in the language you're trying to change to?  
- Are you changing to the "other" language in the page tab of the page or in the Kentico UI at the bottom of the content tree?  
- Have you output the value of the localization context macro to determine the actual culture the site is running in?  {% LocalizationContext.CurrentCulture.CultureCode %}