Don't give up completely on Skye. It has become the hottest tourist destination in Scotland, outside of Edinburgh. If all else fails, try calling the Tourist Information office in Portree, and give them the dates you expect to be there. Most of the B&Bs on Skye do not list on the internet. They don't need to - they know that they'll most likely always be full. The TI office should be able to put you in contact with B&Bs that are not full yet. Expect to pay about 80 to 90 pounds per night. If Portree doesn't know of anything, you could try the TI office in Broadford. They cover more of south Skye.
Telephone numbers are (from the U.S.):
Portree: 011 44 1478 612992
Broadford: 011 44 1471 822713
If you're planning to take the Jacobite from Fort William to Mallaig, you can save time by returning on the regular train.
If the Skye part of your holiday falls through, you could take the A9 from Inverness to the A938 at Carrbridge (a very nice small town), then the A95 to Grantown on Spey, then the A939 south through Tomintoul to Ballater, which will put you within a few miles of Balmoral Castle.
If you're staying in Nairn, you could take the A939 all the way to Ballater. If you're going to Balmoral, you should also visit Crathie Kirk, which is just across the street. It's the church that the family attends when they're in Balmoral on summer hols.
Once you leave Balmoral, you can take the A93 east to Aberdeen. Just past Banchory is Crathes, one of the best of the Scottish baronial castles in Aberdeenshire. The gardens at Crathes are gorgeous at this time of year. From Crathes, you can take the A957 (the Slug Road) to Stonehaven, for Dunnottar Castle. You should have no trouble at all finding reasonably priced accommodation in the Stonehaven - Aberdeen area, as it doesn't register in the RS bible. Only problem would be if there is a major oil conference in Aberdeen while you're there.
As you're still up in the air for day 7, you could take the coast road (A92) out of Stonehaven, for Montrose and Arbroath. Once you cross the Tay Bridge at Dundee, you could visit St. Andrews, which is great for its historical aspect, even if you have no interest in golf. Out of St. Andrews, you could then take the A917 for the East Neuk of Fife, and visit the charming fishing villages of Crail, Anster, Pittenweem, and St. Monans. That will put you within striking distance of the Forth Road Bridge, and dear Auld Reekie.
Whatever you end up doing, and whatever you end up seeing, have a wonderful time!