The following works for me using an EasyPIC5 board with the LCD on PORTB, 18F4550 with 20Mhz xtal (mainly as that's what I'm using for a current project and couldn't be bothered to change the PIC !)

Code:
ASM  ; 18F2550/4550, 20mhz crystal
   __CONFIG    _CONFIG1L, _PLLDIV_5_1L & _CPUDIV_OSC1_PLL2_1L & _USBDIV_2_1L
   __CONFIG    _CONFIG1H, _FOSC_HSPLL_HS_1H
   __CONFIG    _CONFIG2L, _PWRT_ON_2L & _BOR_OFF_2L & _VREGEN_ON_2L
   __CONFIG    _CONFIG2H, _WDT_ON_2H & _WDTPS_512_2H
   __CONFIG    _CONFIG3H, _PBADEN_OFF_3H
   __CONFIG    _CONFIG4L, _LVP_OFF_4L & _XINST_OFF_4L
ENDASM

DEFINE OSC 48
TRISB = 0                   ' Make PORTB all outputs
CMCON = 7                   ' Disable comparator


;----[LCD definitions]------------------------------------------------------
DEFINE LCD_DREG  PORTB          ' LCD Data port
DEFINE LCD_DBIT  0              ' starting Data bit (0 or 4)
DEFINE LCD_EREG  PORTB          ' LCD Enable port
DEFINE LCD_EBIT  5              '     Enable bit  (on EasyPIC 5 LCD)
DEFINE LCD_RSREG PORTB          ' LCD Register Select port
DEFINE LCD_RSBIT 4              '     Register Select bit   (on EasyPIC 5 LCD)
DEFINE LCD_BITS  4              ' LCD bus size (4 or 8 bits)
DEFINE LCD_LINES 2              ' number of lines on LCD
DEFINE LCD_COMMANDUS 2000       ' Command delay time in us 
DEFINE LCD_DATAUS 50            ' Data delay time in us 

LCDOUT $FE,1                ' clear screen 
LCDOUT $FE,$80,"LCD Prototype MJ"  

                            ' Use $Fe,$C0 to address the second line
LCDOUT $FE,$C0,"Timer testing"  
pause 5000
LCDOUT $FE,$C0,"             "

Start:                      ' Program starts here
                            

goto start
                            
end
Using DEFINE OSC 20 I had erroneous results on the LCD, so it's obviously a timing issue with your 4MHz resonator.