aznkix , it generally could be done. What i'll suggest before doing so would be to look up the datasheets for both memory chips and ensure that each pin corresponds to each other with the same i/o function.
There is a very useful tutorial on S1mp3 wiki here
http://wiki.s1mp3.org/How_to_add/change_a_memory_chip
Although it's adding/changing a memory chip on a player itself. But the theory is the same as for a removable flash device.