You could try wine but I would be quite surprised if it worked well for crystaltile2 (having seen various pieces of source code at points I am surprised it works as well as it does).
There are a handful of programs made in Java (Lowlines' console tool probably being the most notable) and many are open source though I do not expect much will happen there without a lot of effort (I doubt winelibs will do much for you). A handful of more game specific tools are available in python.
Ndstool is made for linux though (it is part of devkitpro after all,
http://wiki.birth-online.de/know-how/hacking/nintendo-ds/ndstool ), emulators are available, assembly tools are not quite as nice but still there (most of use devkitpro/GCC at various levels), hex editors (I have not really put linux ones through their paces but they are functional enough*) and should be able to get basic tile editing done. Not sure what there is in terms of a GBA/DS capable tile editor for linux these days (whether you can get
http://code.google.com/p/tiledggd/ working or not remains to be seen but I am more confident with WINE there).
*bless for general use and
http://www.romhacking.net/utilities/207/ might be worth a look if you have to play with tables.
Compression tools should already be available in various forms from existing binary/compiled things to source code to java to things that will definitely run on wine/mono.
Basically ROM hacking is windows only or do it yourself for the most part though in the case of the DS you can still get quite a lot done. Few will have any valid objections to trying to change this but it is the case.
Also throughout all of this it should be noted that serious emulation and a few compression searching methods aside ROM hacking is not really a system killer so you can do a lot with a low powered VM if you want to.