I started playing around with BASIC at random on the PET, and a few years later had a Commodore 64 where I learned much more.
I remember having two books which contained a basic storyline, but had coding problems ranging from fixing the code to writing a lock for a door (or a program that would test all combinations, etc) but for years haven't had the slightest idea of where the books went (and neither do my parents.)
They were written for young adults, and general enough to work on any BASIC (at the time C64, Apple II and Atari 400/800 were the targets)
Does anyone know of these, or something similar? They are exactly the sort of thing the OP needs. (That being said, BASIC may no longer be the best language to start with, but aside from provided code, these books would have worked just as well with Ruby/Python/Perl/etc...