Did you try un-linking and re-linking the characters (dragging the portraits)? All non-lead character in a group should follow, unless the leader is sneaking.
I take it it doesn't matter which companion you switch to, or who you choose for the main character?
Try verifying local files: in the Steam library, right click on the game and select Properties, switch to the Local Files tab and then click on the 'Verify Integrity of Game Cache...' button.
Try creating a new profile, then starting a new game to check.
