Brain, the way you think (describe) package workbook should work, is actually the way they do work (most of the time). Our distribution channel is all packaged workbooks, we don't have/use server. And it doesn't matter if I package a Live Connection or an extract. So I suspect there's something else going on. First you should understand that a packaged workbook is really a zip file just with a different name. So you can use any zip utility to open it up and see the folder structure and even open up the data sources.
I'm just going to take a shot in the dark and guess your data source is a cube or something else other than a spreadsheet or database. (?) Whatever the source, you probably should open a file with customer support, they'll take care of you.