Feelies - Nuts & Bolts comes with a foldable blueprint of Mumbo's machines and some of the characters from the game.
Franchise Killer: Nuts & Bolts not only did this for Banjo-Kazooie, but the game's poor performance also killed off the sequels to Conkers Bad Fur Day, and killed off what was left of the original Rare. During and after the production of this game, many of Rare's major players (such as the Stamper bros. and Grant Kirkhope) left and this game's failure led Microsoft to restructure and repurpose Rare into making Kinect games.
Un-Canceled: "Stop 'N' Swop" was added between Nuts & Bolts and the XBLA release of the original game. Unsurprisingly, this was massively nerfed to unlocking minor cosmetic parts in N&B. It was also implemented into the XBLA release of Tooie, in which the feature is used as it was previously intended: having both games on your hard drive unlocks the ability to collect those items in Kazooie, which you can then use in Tooie for rewards. Numerous jokes are made about how long this took (such as Banjo mentioning he's been carrying the eggs for the last ten years).
Urban Legend of Zelda: Stop 'N' Swop. While the rumour had a basis in a real plan of the developers, the lack of implementation lead to wildly varying rumours as to what you could do to access the stubs left behind, amplified by all the teases left around through the years after. It didn't help that the credits shamelessly teased you with the eggs and key. Or that they left in unnecessarily long codes for the sandcastle to actually be able to get them (and about three others they didn't show).
Stop 'N' Swop. Also, there's several signs that the first game was meant to have some worlds that never panned out; Gobi mentions going to "the lava world" (he finally makes it there in Tooie), and one picture in Banjo's house shows him in a foresty area full of mushrooms (eventually reworked as Donkey Kong 64's Fungi Forest, so sayeth Rare).
There was also a level called "Hammershark Island", which apparently wound up being merged with Treasure Trove Cove. Given that there's a cheat to unlock Treasure Trove Cove even though the cheat room is there, it could be that Hammershark Island originally held the cheat sandcastle while Treasure Trove Cove came later.
Originally Kazooie wasn't even a part of Rare's original plan for the game but Rare wanted to give Banjo some moves and have them make sense such as traversing steep slopes and since Banjo still had a backpack they decided to put a bird who became Kazooie in there in order to make Banjo be able to perform those moves and have it make sense.
Eventually when the project was moved to the N64 Rare dropped the pirate theme and story entirely in favor of a more fairy tale style one which was about Banjo and his girlfriend Piccolo (who eventually became his sister Tooty) watching a concert at Spiral Mountain when a giant (who became Gruntilda in the final version) came scared off everyone and kidnapped Piccolo while Banjo was knocked out and an egg which Kazooie hatched from told Banjo about the events concerning the giant's attack while he was out cold. Also, the Giant's Lair looked much different than Gruntilda's Lair.
Wumba was also supposed to be the original role for Mumbo.
Banjo-Threeie, a next gen-platforming experience, teased here never came to pass. Instead Rare decided on a Genre Shift and added vehicle based gameplay.
Witchy World and Glitter Gulch Mine were meant to appear in the first game.
With the exception of two worlds in Banjo-Tooie (Mayahem Temple and Witchyworld), all of the stage themes in Banjo-Kazooie and its sequel begin in the musical key of C (Major/Minor notwithstanding).
Of the ten worlds in Banjo-Kazooie, including Spiral Mountain, six of the themes are in major, and four are in minor. Of Banjo-Tooie's nine worlds, again including Spiral Mountain, only three are in major, and six are in minor. This contributes significantly to Banjo-Tooie's darker tone, compared to its predecessor.
In Mad Monster Mansion in the original game, there's a piece of music on Motzand's giant organ in the chapel. If you happen to take out an instrument and play (or just sightread and whistle) the musical notes, you'll find that the tune represented is Mad Monster Mansion's level music. Particularly fitting, since the church's music itself is Mad Monster Mansion's music played by an organ.
Captain Blackeye, the pirate in Jolly Roger's Lagoon in Tooie, was one of the original characters of the game that became Banjo-Kazooie. The original game was entitled Dream; the game was initially for the SNES but the console was on its last legs and Captain Blackeye was an antagonist to the protagonist named Edison with a wooden sword. At one point Banjo and a dog were just secondary characters until Rare felt that Edison was too much of a generic character so they made the dog the main lead, then a Rabbit, and finally Banjo was made the lead character. That was referenced in Tooie, where Blackeye states he had a dream, and how a bear who looks like Banjo stole his glory.
This was, in fact, unintentional - the appearance of Banjo and Tiptup in DKR was an Early-Bird Cameo. Banjo's title was initially planned to be released before DKR, but in 1997 Rare found themselves without a game ready for the holiday season, so they had to pick from then-in-development DKR, B-K, and Conker (not yet in its Bad Fur Day form) to quickly finish before Christmas rolled around. Obviously, they settled on DKR.
The original game initially featured a full 15 worlds, but 6 were Dummied Out. Four of those, however, were eventually used in other games: The "lava world" that Gobi mentions was the original version of Hailfire Peaks (called Mount Fire Eyes then), eventually moved to Tooie. Fungus Forest, a world only visible as a picture in Banjo's house (step inside and look at the walls), eventually became Donkey Kong 64's Fungi Forest. An unnamed ore mine level became Glitter Gulch Mine in Tooie. WitchyWorld was originally a stage in Banjo-Kazooie, but was removed and later re-added to Tooie.
Banjo-Kazooie and Banjo-Tooie were partially developed side-by-side. Because of this, some levels were traded around between the games prior to completion. Notably, Rusty Bucket Bay was moved from 'Tooie to 'Kazooie, and as stated above, Glitter Gulch Mine and WitchyWorld were both moved from Kazooie to Tooie because the developers believed both would benefit from longer development and the increased level size that became possible in Tooie.
Banjoland in Nuts & Bolts includes at least one exhibit from every level in the first two games. (Some of the objects/exhibits appear in multiple levels in the original games, but they only tend to represent one in Banjoland. There are also additional miscellaneous props from the levels scattered around the level, but there is only one main exhibit surrounding each level.) The primary exhibits are:
Stonehenge from Mumbo's Mountain
Captain Blubber's ship and a sunken treasure horde from Treasure Trove Cove
Clanker from Clanker's Cavern
A wooden statue of Tanktup from Bubblegloop Swamp
The (now melted) snowman from Freezeezy Peak
A pyramid from Gobi's Valley
Part of the mansion and several animate gravestones from Mad Monster Mansion
The Rusty Bucket ship from Rusty Bucket Bay
The giant tree from Click Clock Wood
A kickball field from Mayahem Temple
An ore pile and mine carts from Glitter Gulch Mine
The Cactus O' Strength from WitchyWorld
The UFO from Jolly Roger's Lagoon
Terry's nest from Terrydactyland
Loggo the toilet from Grunty Industries
Boggy's igloo from Hailfire Peaks
The mountain and the giant trashcan from Cloud Cuckooland
Banjoland, being a pseudo-museum, includes a number of signposts offering tidbits about each exhibit from the earlier games. Each of the signposts is numbered, with an apparent total of 20. However, there are only 19 posts in the level. The 20th, which would be #14 in the sequence, is supposed to be for Terry's Nest from Terrydactyland in Banjo-Tooie, according to the game files. Hacking has revealed that it is listed in the registry along with the other signposts, but the text has yet to be located, if it is in fact there to be found.
One such signpost claims that Canary Mary's races originally required rotating the N64's control stick instead of rapidly tapping B, and that this was changed when the friction caused playtesters' palms to become raw. This is a joke in reference to Mario Party, which actually did have such challenges, in which players would use their palms instead of their thumbs to rotate the stick, indeed leading to scorched palms. While not confirmed, the Canary Mary challenges more than likely always used Button Mashing.
Such rotation also led the controllers to an early grave...
In Banjo-Kazooie's "Grunty's Furnace Fun" quiz challenge, one possible question was "What is on top of the Rusty Bucket's third funnel [a.k.a. smokestack]?" The answer was that the ship has no third funnel. In Banjoland, it suddenly has - you guessed it - three funnels.
Early in the development of Nuts & Bolts, Mumbo's Mountain from the original Banjo-Kazooie was planned to potentially make a returning appearance as its own level, similar to what happened with Spiral Mountain. Grant Kirkhope, the composer for the series, created a 4-minute orchestration of the classic Mumbo's Mountain theme for use there. The level was Dummied Out long before the game began solid development however, and the song went unused in-game, instead appearing in the original teaser trailer and one additional later trailer. The full piece is still present in the game files.
On the subject of cut music, in the original game there's the infamous "Advent", an unfinished-sounding piece that sounds utterly unlike anything else in the game. There were quite a few fan theories as to what the damn song was actually meant for, but the most popular was that it was for the Dummied Out level Fungus Forest. Rare has officially confirmed that it was for the Giant's Lair (see below.)
The rock remix of the B-K theme heard in the Nuts & Bolts trailers was based on a similar arrangement heard on a radio in Rare's earlier title Kameo: Elements of Power. The full version is present on the N&B game disc, but is not used anywhere in the game, much like the Mumbo's Mountain theme mentioned above.
Prior to the release of Banjo-Kazooie, a promotional VHS tape was distributed showcasing video clips of an early build of the game, with a narrator describing each world. In describing Rusty Bucket Bay, the narrator incorrectly gives the name of the ship as the HMS Gruntilda, when both Banjo-Kazooie and Banjo-Kazooie: Nuts and Bolts give the name as simply the Rusty Bucket. This also carries the implication that the ship is part of the British Royal Navy, which it clearly is not.
In Grunty Industries, there are numerous crates that say they are bound for Twycross, England. Twycross is a civil parish in Leicestershire, and is where Rare is based. Both the BK and BK:N&B versions of the Rusty Bucket list Twycross as their home port; an oddity considering Twycross is completely landlocked.
The chanting in the music that soundtracks Tooie's Mayahem Temple level sounds like Mumbo's usual gibberish, but if you listen carefully, you realise that it's actually saying "Come and have a go, if you think you're hard enough". This is a popular term often associated with football in the UK, appropriately enough for the level's kickball elements, and was inserted by composer Grant Kirkhope as a joke.