Okay,
Here's an example, you can try:
// ===================================================================
// Example for LCD Keypad Shield from  http://www.nuelectronics.com/
// -------------------------------------------------------------------
// * Modified to use a patched LiquidCrystal library 
// * Alternative routine to detect keys
// ===================================================================
#include <stdio.h>
#include <LiquidCrystal.h>
LiquidCrystal lcd(8, 14, 9, 4, 5, 6, 7);
// ===================================================================
// hardware settings
#define rightKey  0
#define upKey     1
#define downKey   2
#define leftKey   3
#define selectKey 4
#define NUM_KEYS  5
// ===================================================================
// Program parameters
#define minOpt1   5
#define maxOpt1 999
int valueOpt1 = 15;
#define minOpt2   1
#define maxOpt2  99
int valueOpt2 = 10;
#define programMode1 0
#define programMode2 1
#define programMode3 2
int programMode    =  programMode1;
boolean inMainProgram  =  false;
int programmSequence = 0;
#define sequenceModeSelect  0
#define sequenceModeOption  1
#define sequenceModeProgram 2
// first menu line - description of menu level
char sequenceHeader[3][17]  = {"Mode select     ", "Option select   ", "Program start   "};
// second menu line - mode select
char sequenceModes[3][17]   = {"  Mode 1       >", "< Mode 2       >", "< Mode 3        "};
// second menu line - options settings
char sequenceOptions[3][17] = {"Option 1:  ", "Option 2:   ", "no options      "};
void setup() 
{ 
    // initial lcd display while initialize and pc detection
    lcd.clear();
    lcd.print("Freeduino  0.0.1");
    
    programmSequence = sequenceModeSelect;
    inMainProgram = false;
    
    delay(2000);
    updateScreen();
}
// ===================================================================
// main loop with new key detection
int keyEvent  = -1;
int lastEvent = -1;
int countEvent = 0;
//Key message
char msgs[5][3] = {
    "> ", 
    "^ ", 
    "v ", 
    "< ", 
    "* " };
void updateScreen()
{
    lcd.clear();
    lcd.print(sequenceHeader[programmSequence]);
    lcd.setCursor(0,1);
    switch(programmSequence)
    {
        case sequenceModeSelect:
            menuModeSelect( keyEvent );
            break;
        case sequenceModeOption:
            menuOptionSelect( keyEvent );
            break;
        case sequenceModeProgram:
            break;        
    }
}
void loop() 
{
    int keyEvent = detectKey();
    if (keyEvent >= 0)
    {
        switch (keyEvent)
        {
            case upKey:
                if (!inMainProgram)
                {
                    if (programmSequence > sequenceModeSelect)
                        programmSequence--;
                    updateScreen();
                }
                break;
            case downKey:
                if (!inMainProgram)
                {
                    if (programmSequence < sequenceModeProgram)
                        programmSequence++;
                    updateScreen();
                }
                break;
            case rightKey:
            case leftKey:
                if (!inMainProgram)
                {
                    switch (programmSequence)
                    {
                        case sequenceModeSelect:
                            menuModeSelect( keyEvent );
                            break;
                        case sequenceModeOption:
                            menuOptionSelect( keyEvent );
                            break;
                        case sequenceModeProgram:
                            break;
                    }
                }
                break;
            case selectKey:
                lcd.setCursor(0, 1);
                if (lastEvent != keyEvent)
                {
                    lastEvent = keyEvent;
                    countEvent=0;
                }
                else
                    countEvent++;
                lcd.print(msgs[keyEvent]);
                lcd.print(countEvent);
                break;
        }
    }
}
// ===================================================================
// Menu tools
void menuModeSelect( int keyEvent )
{
    switch (keyEvent)
    {
        case rightKey:
            if (programMode < programMode3)
                programMode++;
            break;
        case leftKey:
            if (programMode > programMode1)
                programMode--;
            break;
    }
    lcd.setCursor(0,1);
    lcd.print( sequenceModes[programMode] );
}
void menuOptionSelect( int keyEvent )
{
    char cbuf[4] = "   ";
    lcd.setCursor(0,1);
    lcd.print(sequenceOptions[programMode]);
    switch (keyEvent)
    {
        case rightKey:
            switch (programMode)
            {
                case programMode1:
                    if (valueOpt1 < maxOpt1)
                        valueOpt1++;
                    break;
                case programMode2:
                    if (valueOpt2 < maxOpt2)
                        valueOpt2++;
                    break;
            }
            break;
        case leftKey:
            switch (programMode)
            {
                case programMode1:
                    if (valueOpt1 > minOpt1)
                        valueOpt1--;
                    break;
                case programMode2:
                    if (valueOpt2 > minOpt2)
                        valueOpt2--;
                    break;
            }
            break;
    }
    switch(programMode)
    {
        case programMode1:
            if (valueOpt1 > minOpt1)
                lcd.print("<");
            else
                lcd.print(" ");
            sprintf(cbuf,"%3d",valueOpt1);
            lcd.print(cbuf);
            if (valueOpt1 < maxOpt1)
                lcd.print(">");
            else
                lcd.print(" ");
            break;
        case programMode2:
            if (valueOpt2 > minOpt2)
                lcd.print("<");
            else
                lcd.print(" ");
            sprintf(cbuf,"%2d",valueOpt2);
            lcd.print(cbuf);
            if (valueOpt2 < maxOpt2)
                lcd.print(">");
            else
                lcd.print(" ");
            break;
    }
}
// ===================================================================
// Lcd tools
void clearLine(int line)
{
    lcd.setCursor(0,line);
    lcd.print("                ");
    lcd.setCursor(0,line);
}
// ===================================================================
// Define a custom char in lcd
int defineCharacter(int ascii, int *data) {
    int baseAddress = (ascii * 8) + 64;  
    // baseAddress = 64 | (ascii << 3);
    lcd.command(baseAddress);
    for (int i = 0; i < 8; i++)
        lcd.write(data[i]);
    lcd.command(128);
    return ascii;
}
// ===================================================================
// Convert ADC value to key number
int adc_key_val[NUM_KEYS] ={ 30, 150, 360, 535, 760 };
int get_key(unsigned int input)
{
    int k;
    for (k = 0; k < NUM_KEYS; k++)
    {
        if (input < adc_key_val[k])
            return k;
    }
    if (k >= NUM_KEYS)
        k = -1; // No valid key pressed
    return k;
}
// ===================================================================
// new key detection routine, without delays!
int     lastKeyEvent = 0;
int     curKeyEvent  = 0;
int     keyToReturn  = 0;
boolean keyToProcess = false;
int     adc_key_in   = 0;
int detectKey()
{
    keyToReturn = -1;
    adc_key_in = analogRead(0);         // read the value from the sensor  
    curKeyEvent = get_key(adc_key_in);      // convert into key press
    if (curKeyEvent != lastKeyEvent)
    {
        if (!keyToProcess) 
        {
            lastKeyEvent = curKeyEvent;
            keyToProcess = true;
        }
        else
        {
            keyToReturn = lastKeyEvent;
            lastKeyEvent = -1;
            keyToProcess = false;
        }
    }
    return keyToReturn;
}
// ===================================================================
The menu will have 3 levels
- Choose program mode
 1st and 2nd mode has options, 3rd not
- Select the value
 1st program mode has a value between 5 and 999
 2nd program mode has a value between 1 and 99
 3rd program mode don't have an option
- Start your program
About the menu and LCD keypad:
- you have to patch LiquidCrystal (I told before)
- i use an alternative routine to detect a key pressed,
 without blocking the main loop, so it looks a bit different
So copy & paste, compile, upload and test and then try to read and learn 
Cheers
KiWiX
--modified 23:55
I forget, it works different as you mentioned above:
- with right and left you change the values
- with up and down you change the menu level
But if you understand my code, you could simple change the behavior 
The size of the sketch is ~5kB
--modified 23:58
There was a small bug in line 193
-- modified 23:59
if someone has tips to optimize this code, please post them here