I would suggest You take a look at:

http://204.210.50.240/techref/default.asp?url=microchip/picboard.htm

It's a pc-keyboard 'emulator' I made awhile ago,
anyway the keyboard matrix routines/design should be useful,
I use an 4051 ( analouge multiplexer ) as adress out 
, when an column is adressed ( pulled down = 0V ),
I read the inputs ( 4 ). For my project it was enough
with internal weak pullup, but depedning on cable length
etc. You maybe want to use stronger pullups ( 2.7 kohm I think you used
).
The reason for the analogue multiplexer if that non-adressed
columns are free floating ( or indirectly pulled-up ).

Best regards Tony KŸbek