I've never come across that error before, but it sounds like the executable you're debugging is built for a different architecture/processor than the one you are using to debug. Since you're on Linux, use the file command:
If those two commands return different results you may have problems. Are you doing embedded work? Perhaps GDB is 32-bit and the other file is 64-bit. More details would be necessary, like copy-pasting a transcript of your GDB session.
$ file /usr/bin/gdb
/usr/bin/gdb: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.18, stripped
$ file /path/to/file/you/are/debugging