I've been trying to come up with a formula/macro to do this for a
long time but I can't seem to figure it out. You all seem very
knowledgeable so maybe you can take a stab at it.

Here's an example of what my spreadsheet looks like: (explanation
below)

Sheet1: [Fruit]
Column A Column B Column C
ITEM (duplicates) COLOR (duplicates) PRODUCT # (only 1)
Apples Green 1111
Apples Red 1112
Apples Pink 1113
Grapes Red 1114
Grapes Green 1115
-------------------------------------------------------
Sheet2: [Vegetables]
Column A Column B Column C
ITEM (duplicates) COLOR (duplicates) PRODUCT # (only 1)
Lettuce Red 2221
Lettuce Green 2222
Potatoes Brown 2223
Potatoes Red 2224
-------------------------------------------------------
Sheet3: [Look-Up]
Column A Column B Column C Column D
FRUIT/VEGETABLE ITEM COLOR PRODUCT #
[user defined] [user defined] [user defined] <FORMULA HERE

I want the user to input these 3 values and then the formula will
generate the PRODUCT #. I've tried countless Count/Index/Match
combinations but none seem to work; any suggestions? Sorry for the
lengthy explanation...

Thanks - Dan