I discovered this once when I was trying to add a lookup column pointing to a very extensive list of countries, and a few other things, such as regions, divisions, etc.
The purpose of using Choice columns is for most part to force the user to make selections from a predefined list, so as to avoid duplicate values or mispellings.
Why would Microsoft not allow pointing lookup columns to choice columns is beyond me. But well, let's dive in the work-around I found. By the way, this works for both MOSS 2007 and SharePoint 2010.
So the first thing we need to do is create a custom list where to host the Choice column.
I'm going to designate is a Calculated value column. And then I'm going to insert the Country column.
The next thing you need to do is determine the data type that will be returned from the column. For my example, I'm good using Single line of text; therefore, I won't change the default value suggested by SharePoint.
Create a new column on this second list and select Lookup as the type of information.
Make any additional selections you may need (such as whether to require that this column must contain information).
Select your first custom list, the one where you created the calculated value column at the Get information from drop-down list.
And then select the Calculated value column from the list (where it says In this column).